题解 P3912 【素数个数】

critnos · 2019-09-07 16:41:53 · 题解

在看完题解后，我彻底被吓蒙了

在看完评论

@a1204675546：

不知道怎么说，，，这道题可以直接用线性筛，，，，，数据有点水。

后，我才心定了一些，打了一波普通筛（没错，不是欧拉筛）

然后奇迹般的过了

#include <bits/stdc++.h>
using namespace std;
bool a[100000005];
int main()
{
    int i,n,j,s=1;
    cin>>n;
    if(n<2)//特判，要不然会输出1
    {
        cout<<0;
        return 0;
    }
    for(i=3;i*i<=n;i+=2)//优化1：不筛2的倍数
    {
        if(a[i]==0)
            for(j=i*i;j<=n;j+=i*2)//优化2：从i*i开始，每次加i*2，配合优化1使用
                a[j]=1;
    }
    for(i=3;i<=n;i=i+2)//优化3：仍然配合配合优化1使用
        s+=!a[i];
    cout<<s;
}