题解 P3912 【素数个数】 欧拉筛水过

· · 题解

其实是闲的没事找个水题发本蒟蒻的第一篇题解是一个简单的线性筛（欧拉筛法）模板...

时间复杂度已经降到O（n）.

比较坑的是1，要特判不是素数，一开始被坑 WA两个点.

上代（mu）码（ban）...

#include<iostream>
#include<cstdio> 
#include<cmath>
#include<cstring>
using namespace std;
const int maxn=100000001;
int prime[maxn];      //就是个素数表
bool sf[maxn];        //判断这个数是不是素数，sf[i]中的i是从1到maxn的数
void sushu(){         //核心 欧拉筛代码
    int num=0;        //num 用来记筛到第几个质数
    memset(sf,true,sizeof(sf));
    for(int i=2;i<=maxn;i++){          //外层枚举1~maxn
        if(sf[i]) prime[++num]=i;      //如果是质数就加入素数表
        for(int j=1;j<=num;j++){       //内层枚举num以内的质数
            if(i*prime[j]>maxn) break; //筛完结束
            sf[i*prime[j]]=false;      //筛掉...
            if(i%prime[j]==0) break;   //避免重复筛
        }
    }
    sf[1]=false;
    sf[0]=false;  //1 0 特判 
}
int main(){
    sushu();
    int m,cnt=0;
    cin>>m;
    for(int i=1;i<=m;i++)
        if(sf[i]) cnt++;
    cout<<cnt; 
    return 0;
}