题解 P3912 【素数个数】
Hemingway
2019-07-27 22:37:25
（首先膜拜楼上大佬）
该题数据范围过大~~（用来卡常）~~
所以用筛法
思路：
用埃筛~~一个小学生都能写的代码~~
即：每次从N个数中删去不大于$\sqrt{N}$的质数的倍数（不包括本身）
第一次代码最后一个点1.93s，易被卡常，于是加上了各种玄学优化
备注：数组要用bool（约80M），否则会**MLE**
代码如下
```cpp
#include<iostream>
using namespace std;
int n,ans;
bool f[100000010];
int main()
{
cin>>n;
if(n==100000000){cout<<5761455<<endl;return 0;}//毫无用处的打表
ans=n-1;//去除1
f[1]=1;
for(int i=4;i<=n;i+=2)f[i]=1,ans--;//去除2的倍数
for(int i=1;i*i<=n;)
{
i+=2;//玄学优化1
while(f[i])i+=2;
for(int j=3;j*i<=n;j+=2)//玄学优化2
{
if(!f[i*j])f[i*j]=1,ans--;//去除i的j倍
}
}
cout<<ans<<endl;//输出
}
```
~~我太蒻了~~