有以下的两条性质：
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]; } }
原文：https://www.cnblogs.com/lightmain-blog/p/11139586.html