题解 P3912 【素数个数】

· · 题解

线性筛素数，挺好的呀，代码那么好写。

主要思路就是线性筛素数，每次新找到一个，ans--,ans最开始为N，只不过不加一些优化，会超时；

  1. 快读。。。（好像并没有什么用。。。）

2.因为第一个筛2的倍数，显然2的倍数是可以直接筛掉，不用涉及与其他的关系，所以直接筛掉。

就直接用 ans - =ans/2;

ans++; 因为2是个质数所以ans++;

3.最内层的循环从i*i开始就行了，因为2*i，3*i...（i-1)*i都已经被筛过了

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int f=1,x=0;
    char ch;
    do{
      ch=getchar();
      if(ch=='-')
         f=-1;
    }while(ch<'0'||ch>'9');
    do{
       x=x*10+ch-'0';
       ch=getchar();
    }while(ch>='0'&&ch<='9');
    return f*x;
}
int n;
int ans;
bool p[100000001];
int main()
{
    n=read();
    if(n==1)//特判
    {
        cout<<0<<endl;
        return 0;
    }
    ans=n; 
    ans-=ans/2-1;
    ans--;//把二的倍数筛掉
    p[1]=true;
    for(register int i=3;i<=sqrt(n);i++)
    {
         if(p[i]==false)//只有质数我们才把他的倍数筛了，因为合数的倍数早就被判断过了
        {
            for(register int j=i*i;j<=n;j+=i)
            {
                if(p[j]==false&&j%2!=0) ans--;//如果他还没有被更新成合数，且他不为2的倍数（因为2的倍数，我们直接就筛了
                                                                                //没有用布尔数组
                    p[j]=true;
            }
        }
    }
    printf("%d",ans);
}