【模板】线性筛素数

_caiji_ · 2021-06-12 09:53:53 · 个人记录

template<int N> class LineSiever{
    private:
        bool isp[N+10];
        int n,p[N+10];
    public:
        LineSiever():n(0){
            memset(isp,1,sizeof isp);
            isp[0]=isp[1]=0;
            for(int i=2;i<=N;i++){
                if(isp[i]) p[++n]=i;
                for(int j=1;j<=n&&1LL*i*p[j]<=N;j++){
                    if(isp[i*p[j]]=0,i%p[j]==0) break;
                }
            }
        }
        operator int(){return n;}
        bool operator()(int x){return isp[x];}
        int operator[](int x){return p[x];}
};

LineSiever<100> p;
cout<<p<<endl;//100 内有多少素数
cout<<(p(2)?"Yes":"No")<<endl;//2 是不是素数
cout<<p[3]<<endl;//第 3 个素数（5）
cout<<LineSiever<(int)1e8>()<<endl;//简写求出 1e8 内素数个数