线性筛筛质数
<pre><code class="language-cpp">#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;
}
}
}</code></pre>