求欧拉函数的一般方法：
1.我们知道一个素数p的欧拉函数f(p)=p-1；那么p的k次幂，即n=p^k，则容易证明：f(n)=p^k-p^(k-1)；
证明：已知少于p^k的数有p^k-1，其中与p^k不互质的数有p^(k-1)-1个，分别为（p*1，p*2，p*3，····，p*（p^(k-1)-1））。所以f(n)=p^(k)-1-(p^(k-1)-1)=p^(k)-p^(k-1)。
2.假设p，q为两个互质的数，则：f(p*q)=f(p)*f(q)；
原来这里一直写着一个略字，倒不是因为太简单，而是我没证出来，一开始自己写了一个证明，但后来发现不对，然后一直也没想出如何证，今天看初等数论第三章同余的时候找到了证明，所以赶紧过来整理一下。
证明：这里主要用到了简化剩余系，x1，x2分别通过模m1，m2的简化剩余系，则m2*x1+m1*x2通过模m1*m2的简化剩余系。由于m2*x1+m1*x2通过f（m1*m2）个整数，x1通过f(m1)个整数，x2通过f（m2）个整数，所以f（m1*m2）=f（m1）*f（m2）；
有了以上两个性质，欧拉函数就非常简单了，先对一个数进行整数分解，然后···
下面介绍一种快速的方法：
因为任意正整数都可以唯一表示成如下形式:
k=p1^a1*p2^a2*……*pi^ai;(即分解质因数形式)
可以推出:E(k)=(p1-1)(p2-1)……(pi-1)*(p1^(a1-1))(p2^(a2-1))……(pi^(ai-1))
=k*(p1-1)(p2-1)……(pi-1)/(p1*p2*……pi)=k*(1-1/p1)*(1-1/p2)....(1-1/pk)
ps：在程序中利用欧拉函数如下性质，可以快速求出欧拉函数的值(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);
埃拉托斯特尼筛求欧拉函数：
//phi[i]表示i的欧拉函数
void euler(int n)
{for (int i=1;i<=n;i++) phi[i]=i;for (int i=2;i<=n;i++){if (phi[i]==i)//这代表i是质数{for (int j=i;j<=n;j+=i){phi[j]=phi[j]/i*(i-1);//把i的倍数更新掉}}}
}
直接实现：
int Euler(int n){int m=n;for(int i=2;i*i<=n;i++){if(n%i==0)//第一次找到的必为素因子{m-=m/i;//把是素因子i的倍数的数的数目减掉 i,2i,3i,···,(m/i)*i while(n%i==0)n/=i;//把该素因子全部约掉 } }if(n>1) //还有一个比根号n大的素因子 ,也就是现在这个n m-=m/n; return m;
}
欧拉筛：
