在数论中，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。
——百度百科词条《欧拉函数》
欧拉函数通式：
为了方便编程通常不用这个通式，而用Φ(x)=p1^(n1-1)*p2^(n2-1)* ... *pk^(nk-1)*(p1-1)*(p2-1)* ... *(pk-1)计算，其中p1,p2,..pk为正整数x的质因数，n1,n2,...nk对应质因数的次数。
该式易通过欧拉函数的性质推导出来。首先将正整数n进行质因数分解（小学数学的即视感
另外欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
所以有：
int Euler(int ans1)
{
int res=1;
int ans=ans1;
for(int i=2;i*i<=ans1;i++)
{
if(ans%i==0)
{
//如果找到ans的质因数i
//这里的i一定是ans的质因数,因为一旦找到一个因数i,
//下面的语句就会在ans的质因数分解式里约掉这个因数
//例 ans=36 i=2时 循环语句执行完后ans=9 当i=4时就不会进入循环体
ans/=i;
res*=i-1; //处理函数式中的 ...*(pk-1)项
while(ans%i==0) //处理函数式中的 ...*pk(nk-1)项
{
res*=i;
ans/=i;
}
}
}
if(ans>1)
{
res*=(ans-1);
}
return res;
}