素剩倍筛

#include<bits/stdc++.h> 
using namespace std; 
const int N=1e8+1; 
int las[N],nex[N],sta[N],top; 
bool f[N];
inline void fsbz(int maxe){
    int over=sqrt(maxe); 
    for(int i=2;i;i=nex[i]){ 
        if(i>over){
            break;
        } 
        for(int j=i;j;j=nex[j]){ 
            if(i*j>maxe){ 
                break;
            }
            f[i*j]=1;
            sta[++top]=i*j;
        }
        while(top){ 
            int v=sta[top--];
            nex[las[v]]=nex[v];
            las[nex[v]]=las[v];
        }
    }
} 
int main(){ 
    for(int i=2;i<N;++i){
        nex[i]=i+1,las[i]=i-1;
    }
    las[2]=0,nex[N-1]=0;
    fsbz(N-1); 
    return 0;
}