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

有以下的两条性质：

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];    }}