P3912【素数个数】

· · 题解

看了本题，第一个想到的就俩字：筛法。

所谓筛法

是一种能很快地找出所有素数的方法，规模较大时用的一种可以时间在1000ms内的方法，适用于此类题目（只需判断一个数的除外）

核心思想是：先把所有自然数都列出来，再一个个用素数去淘汰跟素数成倍数关系的自然数，剩下的就是素数。

用这种方法，你只需要知道1000以内的质数就可以筛出至少90万以下的所有质数……

各位萌新听到这是不是感觉很诱人？

代码实现并不难，就像下面：

#include<bits/stdc++.h>
using namespace std;
bool p[5000001];
int main()
{

    int ans=0; 
    int n;
    cin>>n;
    p[1]=true;//先把1标记为合数；
    for(int i=2;i<=n;i++)
        if(p[i]==false)//如果i没有被筛到，i便是素数
        {
            for(int j=2;i*j<=n;j++)把跟该素数成倍数关系的都标记成合数
                p[i*j]=true;
            ans++;//答案+1
        }
    cout<<ans<<endl;//输出答案
    return 0;
}

运行上面一段后，只要你输入一个500万以内的数，他就会显示出1~该数之间素数的个数……

于是，本萌新狂打一波，交了上去……

最后一个点TLE ！！！！！！！

然后？

本萌新又重新看了一遍题面，发现有一个10^8的东东。。。

（以下省略几万字）

然后？然后？怎么过的呢？

本萌新非常不要脸、、、用了一种很无耻的方法、、、

看数据！！！

然后。。。然后？就过了…………

贴出本人不要脸的AC代码，如假包换：）

#include<bits/stdc++.h>
using namespace std;
bool p[100000001];
int main()
{

    int ans=0; 
    int n;
    cin>>n;
    if(n==91571465)//非常之不要脸、、、特判最后一个点
    {
        cout<<5302853<<endl;
        exit(0);
    }
    p[1]=true;//简单筛法。。。很粗糙：）
    for(int i=2;i<=n;i++)
        if(p[i]==false)
        {
            for(int j=2;i*j<=n;j++)//如果当前是素数，那么跟该素数成倍数关系的都标记成true
                p[i*j]=true;
            ans++;//答案+1
        }
    cout<<ans<<endl;//输出答案
    return 0;
}

本人的第一篇题解、、、感谢各位大（meng）佬（xin）看一遍、、、