题解 P3912 【素数个数】

· · 题解

这题是线性筛模版，那么我们来康康两种筛在这题中该怎么做：

欧拉筛：

和普通的欧拉筛没什么区别，唯一的问题就是……

数组肯定开不了这么大。但是，我们知道，素数是很少的，所以数组没必要开那么大，至于具体开多大，自己估摸着开吧（逃

重点：埃筛法：

埃筛法不用开一个数组存素数，所以没有欧拉筛的问题，但是埃筛的时间复杂度比较高，在O(n)和O(n^2)之间（纯属自己推算，如果有误，那就是不对）。所以我们要考虑优化。
我们可以把数分成两类：<=\sqrt{n}和>\sqrt{n}。而这两类又可以分为素数和合数。可以发现，>\sqrt{n}的合数都可以由<=\sqrt{n}的素数筛出来，那么我们就可以考虑省去后半部分的计算。我们注意到，筛掉的是合数，剩下的就是素数了，这题只求个数，不求具体数字，所以只要把n - \sqrt{n}的差再减去合数，就是这部分的素数。那么如果后面可以这么做，前面也可以，所以具体思路就出来了：

  1. 变量s=n-1，即先假设2~n都是质数
  2. 遍历2~根号n，记为i
  3. 如果是质数，那么再遍历n以内i的大于i的整倍数
  4. 如果是未被标记为合数
  5. 记为合数，并将s-1
  6. 否则跳过

这样就能大大减少计算数量，使得效率增加。

上代码：

#include<cstdio>
int n,ans;
bool f[100000000];//标记数组，0为素数，1为合数
int main()
{
    scanf("%d",&n);
    ans=n-1;//同上面讲的s
    for(int i=2;i*i<=n;i++)//遍历2~根号n
    {
        if(!f[i])//如果是素数
        {
            for(int j=i*2;j<=n;j+=i)//遍历n以内大于i的i的整倍数
             if(!f[j])//如果未被标记
             {
                f[j]=1;//标记
                ans--;//素数个数-1
             }
        }
    }
    printf("%d",ans);//输出
    return 0;
}

完结！