The Unknown Way

题解 P3912 【素数个数】

(首先膜拜楼上大佬)

该题数据范围过大(用来卡常)

所以用筛法

思路:

用埃筛一个小学生都能写的代码

即:每次从N个数中删去不大于 $\sqrt{N}$ 的质数的倍数(不包括本身)

第一次代码最后一个点1.93s,易被卡常,于是加上了各种玄学优化

备注:数组要用bool(约80M),否则会MLE

代码如下

#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;//输出
}

我太蒻了


2019-07-27 22:37:25 in 题解