模板 - 数论 - 线性筛 - 新

质数筛

int pri[MAXN],pritop;
bool notpri[MAXN];
//pritop从1开始计数

void sieve1(int n) {
    notpri[1]=1;
    for(int i=2; i<=n; i++) {
        if(!notpri[i])
            pri[++pritop]=i;
        for(int j=1; j<=pritop&&i*pri[j]<=n; j++) {
            notpri[i*pri[j]]=1;
            if(i%pri[j]==0)
                break;
        }
    }
}int pri[MAXN],pritop;
bool notpri[MAXN];