【数论】模板-线性筛素数,欧拉函数,莫比乌斯反演

这里的代码一起实现了线性筛素数,欧拉函数,莫比乌斯反演,也比较好打。

void sieve(){
    fill(isPrime, isPrime + maxn, true);
    mu[1] = 1;
    phi[1] = 1;
    num = 0;
    for(int i = 2; i < maxn; ++i) {
        if(isPrime[i]){
            primes[num++] = i;
            mu[i] = -1;
            phi[i] = i - 1;
        } 
        static int d;
        for(int j = 0; j < num && (d = i * primes[j]) < maxn; ++j) {
            isPrime[d] = false;
            if(i % primes[j] == 0) {
                phi[d] = primes[j] * phi[i];
                mu[d] = 0;
                break;
            }else{
                phi[d] = (primes[j] - 1) * phi[i];
                mu[d] = -mu[i];
        } 
        }
    }
}