欧拉函数（详解）

欧拉函数：对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。例如euler(8)=4，因为1,3,5,7均和8互质。 Euler函数表达通式：euler(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn),其中p1,p2……pn为x的所有素因数，x是不为0的整数。euler(1)=1（唯一和1互质的数就是1本身）。 欧拉公式的延伸：一个数的所有质因子之和是euler(n)*n/2。 欧拉定理：对于互质的正整数a和n，有aφ(n) ≡ 1 mod n。 欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。 若n是质数p的k次幂，φ(n)=pk-p(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。 特殊性质：当n为奇数时，φ(2n)=φ(n) 欧拉函数还有这样的性质： 设a为N的质因数，若(N % a == 0 && (N / a) % a == 0) 则有E(N)=E(N / a) * a；若(N % a == 0 && (N / a) % a != 0) 则有：E(N) = E(N / a) * (a - 1)。 那么如何变成实现欧拉函数呢？下面通过两种不同的方法来实现。第一种方法是直接根据定义来实现，同时第一种方法也是第二种筛法的基础，当好好理解。 可以得到关于欧拉函数的递推关系： 假设素数p能整除n，那么 如果p还能整除n / p, PHI(n) = PHI(n / p) * p; 如果p不能整除n / p, PHI(n) = PHI(n / p) * (p - 1);

由对于一个正整数N的素数幂分解N=P1q1*P2q2…Pn^qn. φ(N)=N(1-1/P1)(1-1/P2)…*(1-1/Pn).* 可以写出以下代码：

但是当求一个区间内的时候上面的方法就不行了，那么我们可以类比以下求素数的优化方法，可不可以用筛法呢？答案是可以！

比如求10以内所有数的φ值： 设一数组phi[11]，赋初值phi[1]=1,phi[2]=2...phi[10]=10； 然后从2开始循环，把2的倍数的φ值*(1-1/2)，则phi[2]=2*1/2=1,phi[4]=4*1/2=2,phi[6]=6*1/2=3....； 再是3，3的倍数的φ值*(1-1/3)，则phi[3]=3*2/3=2,phi[6]=3*2/3=2，phi[9]=.....； 再5，再7...因为对每个素数都进行如此操作，因此任何一个n都得到了φ(n)=n*（1-1/p1)(1-1/p2)....(1-1/pk)的运算

代码：