题解 P3912 【素数个数】

· · 题解

%%% @神云_cloud 大佬

这道题的数据范围很大，到了10^8，所以用一个一个判断素数显然会TLE，所以我们就要考虑其他算法。这个时候我们就会引入一种方便好用的算法：筛。这里介绍两种筛法，都是用筛数来做的，一种八十分（自己乱搞的玄学筛法）和100分（欧拉筛O(n)）的算法（其实还有O(nlogn)的筛法，但是和80分的筛法区别不大，有兴趣的同学可以问问度娘）

80分算法：

#include<bits/stdc++.h>
using namespace std;
const int m=100000000;
bool a[m];
int n,sum=1;
//当n>=2时，至少有一个素数2
int main()
{
    scanf("%d",&n);
    if(n<2)
    {//特判一下当n<2
        cout<<'0';
        return 0;
    }
    for(int j=2;j*2<=n;j++)
    //先筛一边偶数，sum初值已经是一，所以不用考虑2
    {
        a[2*j]=1;
    }
    for(int i=3;i*i<=n;i+=2)
    {//从3开始搜，不考虑2
        if(!a[i])
        {
            for(int j=3;j*i<=n;j+=2)
            //乘三即可，因为偶数已经被筛过了
            {
                a[i*j]=1;
            }
        }
    }
    for(int i=3;i<=n;i+=2)
    {
    //判断是否为素数
        if(!a[i])
        {
            sum++;
        }
    }
    printf("%d",sum);
    return 0;
}

100分算法：

#include<bits/stdc++.h>
using namespace std;
#define m 5800000//10^8的范围大概有5700000多个素数
#define m1 100000000
bool f[m1];//f来判断是否筛过
int n,cnt=0,p[m];//p来存素数个数
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {//欧拉筛素数法模板，可以不重复的筛数
        if(!f[i])
        {//判断i是否被标记，没被标记则为素数
            p[++cnt]=i;
        }
        for(int j=1;j<=cnt;j++)
        {
            if(i*p[j]>n)
            {//若i*p[j]>n则没有再搜的意义（由于欧拉筛是O(n)的，所以没有重复筛，若i*p[j]>n，则后面一定会有另一个数来筛
                break;
            }
            f[i*p[j]]=1;
            if(!(i%p[j]))
            //保证每个数都只被它的最小质因子筛掉。若i%p[j]即p[j]是i的一个质因子，因为p数组是单调递增的，所以后面的i*p[j]会有比p[j]更小的质因子。为了优化算法到此时停止即可
            //再次 %%% @神云_cloud 大佬
            {
                break;
            }
        }
    }
    printf("%d",cnt);
    return 0;
}