作业帮C++(数组)质数统计在自然数 2 n 中,有多少个质数（素数）.输入文件：一个数 n （ 10 ≤ n ≤ 10000000 ）输出文件：一个数,表示 2 n 中的质数个数输入样例：20输出样例：8样例说明：20 以内质数 2
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/15 09:40:14
C++(数组)质数统计在自然数 2 n 中,有多少个质数（素数）.输入文件：一个数 n （ 10 ≤ n ≤ 10000000 ）输出文件：一个数,表示 2 n 中的质数个数输入样例：20输出样例：8样例说明：20 以内质数 2
C++(数组)质数统计
C++(数组)质数统计在自然数 2 n 中,有多少个质数（素数）.输入文件：一个数 n （ 10 ≤ n ≤ 10000000 ）输出文件：一个数,表示 2 n 中的质数个数输入样例：20输出样例：8样例说明：20 以内质数 2
//这是线性筛,O(n)的
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<iostream>
#include<string>
#include<cmath>
#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("%d\n",sum[n]);
}