0~N中的质数的个数约为: N / log2(N)
线性筛法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;//前一万个质数在二十万以内
int primes[N];
bool st[N];
int cnt;
int main(){
//预处理出前一万个质数
for(int i=2; i<N ; i++){
if(!st[i]) primes[cnt++]=i;
for(int j=0; primes[j]*i <=N ; j++) {
st[ primes[j]*i] =true;
if( primes[j]%i ==0 ) break;
}
}
int k;
while(cin>>k){
cout<<primes[k-1]<<endl;//由于是下标,所以要减1
}
}
恳请更正!
是 $\frac{N}{\ln{N}}$
$\frac{N}{\ln{N}}$