题解 P3912 【素数个数】
这题是线性筛素数的模板题啊。。。
线性筛的主要思想是用O(N)的时间判断1...N中的每一个数是不是素数，也就是说用平均O(1)的时间判断一个数是不是质数。
具体实现如下：对从2到sqrt(N)中的每一个素数，将他们的所有倍数标记为合数。这样处理完后，没有被标记为合数的数就是质数了。
请看代码中的详细注释：
#include<cstdio>
using namespace std;
const int maxn=100000000;
bool tf[maxn];//判断是否是素数，如果i是素数，tf[i]是false，反之为true
int n,ans;//ans是最后的结果（你看我连前缀和都懒得写了），初始值为0
int main()
{
scanf("%d",&n);
for(register int i=2;i*i<=n;i++)//枚举i从2...sqrt(N)的所有值，写成i*i<=n的形式更快一些，register很重要
{
if(tf[i])continue;//如果tf[i]是true的话,也就是说i是合数，那么i的所有倍数都被标记过了，直接跳过，保证了时间复杂度
for(register int j=2;i*j<=n;j++)tf[i*j]=true;//对i的所有不大于N的倍数进行标记
}
for(register int i=2;i<=n;i++)if(!tf[i])ans++;//从2...N，如果有一个数是素数，那么ans++
printf("%d\n",ans);
return 0;
}