Question

C++(数组)质数统计在自然数 2 n 中,有多少个质数（素数）.输入文件：一个数 n （ 10 ≤ n ≤ 10000

Answer 1

//这是线性筛,O(n)的

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#define N 10000000

#define FOR(i,a,b) for(i=(a);i<=(b);i++)

#define ROF(i,a,b) for(i=(a);i>=(b);i--)

typedef long long LL;

using namespace std;

bool f[N+10];int sum[N+10],prime[N+10],len=0;

void initprime()

{

int i,j;

FOR(i,2,N)

{

if (!f[i]) prime[++len]=i;

FOR(j,1,len)

{

if (i*prime[j]>N) break;

f[i*prime[j]]=1;

if (i%prime[j]==0) break;

}

}

sum[1]=0;

FOR(i,2,N) sum[i]=sum[i-1]+1-f[i];

}

int main()

{

initprime();

int n;scanf("%d",&n);

printf("%dn",sum[n]);

}