埃氏筛法（Eratosthenes筛选法）
算法基本思想：要得到自然数n以内的全部素数，必须把不大于n1/2的所有素数的倍数剔除，剩下的就是素数。
给出要筛数值的范围n，找出n以内的素数。依次筛选没有质数因子
#include <iostream>
#include <cmath>
using namespace std;
int main(){
bool *p= new bool[1000003]();
int *q=new int[1000001]();
int T,n,count=0;
for(int i=2;i<=1000;i++){
if(p[i]==true)continue;
for(int j=2;j*i<=1000003;j++){
p[i*j]=true;
}
}
for(int i=2;i<1000001;i++){
if(p[i]!=true)count++;
q[i]=count;
}
cin>>T;
while(T--){
cin>>n;
cout<<q[n]<<endl;
}
delete []p,q;
return 0;
}
网友评论