欧拉函数介绍：
在数论中，对正整数n,欧拉函数是少于或等于n你的数中与n互质的数的数目。
通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。 (注意：每种质因数只一个。比如12=2*2*3那么φ（12）=12*（1-1/2）*(1-1/3)=4
#include<iostream> using namespace std; int main(){ int n; while(cin>>n,n){ int ret=1,i; for(i=2;i*i<=n;i++){ if(n%i==0){ n/=i; ret*=i-1; while(n%i==0){ n/=i; ret*=i; } } } if(n>1) ret*=n-1; cout<<ret<<endl; } return 0; }
原文：http://www.cnblogs.com/tz346125264/p/4860915.html