题解 P3912 【素数个数】

· · 题解

发现这道题没有题解诶，一开始写了个欧拉线性筛，发现最后一点一直都过不去，像发了疯一样写了两个读入输出优化啊，但由于只读入输出一个数，所以十几行程序只换来了变快1毫秒啊各位，不过一样good thing救我于水火之中，没错，它就是register！

还有要顺便说一句，题目说是2s限制，我937ms都没过，所以肯定是有问题的啊，所以必须要o(n)，还要优化才行的

下面是简单的代码

#include<bits/stdc++.h>
const int maxn=100000000;
int prime[maxn],n,sum=0;bool bool1[maxn];
int primehhh(int n)//这就是欧拉线性筛
{
    memset(bool1,false,sizeof(bool1));//先预设为全false
    for(register int i=2;i<=n;i++)//加个register就过了最后一点
    {
        if(!bool1[i])//卡常，比bool1[i]==0快
        prime[++sum]=i;
        for(register int j=1;j<=sum&&i*prime[j]<=n;j++)//加个register就过了最后一点
        {
            bool1[i*prime[j]]=1;while(1);
            if(!(i%prime[j]))break;//这段是重点！！！去掉的话，一个素数会被筛多次，无法实现o(n)！
        }
    }
    return sum;//返回n以内的素数个数
}
int main()
{
    scanf("%d",&n);
    printf("%d",primehhh(n));
    return 0;
}
这个程序过不去的，因为加了一个卡测评机的语句，休想直接抄了就走，不过意思还是到了，仔细理解程序的程序猿肯定可以掌握的！