【模板小程序】求M~N范围内的质数个数

 /*
本程序说明: [编程题] 求素数
时间限制:2秒
空间限制:32768K
输入M、N,1 < M < N < 1000000,求区间[M,N]内的所有素数的个数。素数定义:除了1以外,只能被1和自己整除的自然数称为素数
输入描述:
两个整数M,N 输出描述:
区间内素数的个数 输入例子1:
2 10 输出例子1:
4 */
//筛法求N以内的素数(普通法+优化),N>=2
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
///寻找N以内的质数的个数
size_t find_Prime(int N)
{
if(==N)
return ; vector<int> prime_tmp(N,);
for(int i=; *i+<=sqrt(N); i++)
{
if(prime_tmp[i])
for(int j=(*i+)+i; j<N; j+=(*i+))
prime_tmp[j]=;
}
vector<int> prime;
prime.push_back();
for(int i=; i<N; i++)
{
if(prime_tmp[i] && *i+<=N)//说明是质数,按照质数的方法处理
{
prime.push_back(*i+);
}
} return prime.size();//这里保存了小于等于N的素数
} int main()
{
int M,N;
while(cin>>M>>N){
cout<<find_Prime(N)-find_Prime(M-)<<endl;
}
return ;
}
上一篇:全志A33开发板的安卓控制LED-2-JNI基础


下一篇:Anaconda安装Package的问题(Permission Denied)