线性筛筛欧拉函数

#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);
        }
    }
}