首先，要知道欧拉函数是什么！！！
欧拉函数是小于n的数中与n互质（最大公约数为1）的数的数目；
然后，你需要想想
若n是质数p的k次幂，
，因为除了p的倍数外，其他数都跟n互质。
可得
int phi(int n) { int i,rea=n; for(i=2;i*i<=n;i++) { if(n%i==0) { rea=rea-rea/i; while(n%i==0) n/=i; } } if(n>1) rea=rea-rea/n; return rea; }
原文：http://www.cnblogs.com/jhz033/p/5463555.html