递推求欧拉函数的最简单的详解

有以下的两条性质：

if(gcd(i, prime[j]) == 1)
    phi[i * prime[j]] = phi[i] * phi[prime[j]];
    //因为是积性函数。phi[prime[j]]其实就是prime[j]-1。
else
    phi[i * prime[j]] = phi[i] * prime[j];

 所以，可以模仿埃氏筛的方法，来进行递推，顺便同时求出素数表。

F(i, 1, n) phi[i] = i; //相当于not_prime[]的作用
F(i, 1, n) {
    if(phi[i] == i) phi[i] = i - 1, prime[++cnt] = i;
    F(j, 1, cnt) {
        if(i % prime[j] == 0) //等价于gcd(i, prime[j]) ！= 1
            phi[i * prime[j]] = phi[i] * phi[prime[j]];
        else
            phi[i * prime[j]] = phi[i] * prime[j];
    }
}

而如果想要像埃氏筛优化成欧拉筛的方式一样，把这个优化成线性的，同样只需要加一行。

F(i, 1, n) phi[i] = i;
F(i, 1, n) {
    if(phi[i] == i) phi[i] = i - 1, prime[++cnt] = i;
    F(j, 1, cnt) {
        if(i % prime[j] == 0) {
            phi[i * prime[j]] = phi[i] * phi[prime[j]];
            break; //这里加了一行
        }
        else
            phi[i * prime[j]] = phi[i] * prime[j];
    }
}

递推求phi[]的问题就这样解决了！