线性筛筛质数

#include<iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
bool nprime[maxn];
ll pri[maxn];
int cnt = 0;
void phi_sieve(){
    nprime[1] = true;
    for(int i = 2; i <= 1e6; i++){
        if(!nprime[i])    pri[++cnt] = i;
        for(int j = 1; j <= cnt && i * pri[j] <= 1e6; j++){
            nprime[i * pri[j]] = true;
            if(i % pri[j] == 0) break;
        }
    }
}