线性筛筛欧拉函数
<pre><code class="language-cpp">#include<iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
bool nprime[maxn];
ll phi[maxn], pri[maxn];
int cnt = 0;
void phi_sieve(){
nprime[1] = true, phi[1] = 1;
for(int i = 2; i <= 1e6; i++){
if(!nprime[i]) pri[++cnt] = i, phi[i] = i-1;
for(int j = 1; j <= cnt && i * pri[j] <= 1e6; j++){
nprime[i * pri[j]] = true;
if(i % pri[j] == 0){
phi[i*pri[j]] = phi[i] * pri[j];
break;
}
else phi[i*pri[j]] = phi[i] * (pri[j]-1);
}
}
}</code></pre>