————————————————
版权声明：本文为CSDN博主「QLU_minoz」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/QLU_minoz/article/details/81063921
欧拉函数是少于或等于n的数中与n互质的数的数目。
求法：
求解欧拉函数的值可用φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn)，容易知道要对n进行素因子分解。
1）直接实现
int Euler(int n) { //1.直接求欧拉函数的值 int rea=n; for(int i=2; i*i<=n; i++) if(n%i==0) { //第一次找到的必为素因子 rea=rea-rea/i; while(n%i==0) { n=n/i;//把该素因子全部约掉 } } if(n>1) rea=rea-rea/n; return rea; }
素数表实现
先把50 000以内的素数用筛选法选出来并保存，以方便欧拉函数使用，这样，在不考虑筛选法的时间复杂度，而单纯看欧拉函数，其复杂度为O（x），x为O(√¯n）以内素数的个数。
//2.素数表 bool boo[50000]; int p[20000]; void prim() { memset(boo,0,sizeof(boo)); boo[0]=boo[1]=1; int k=0; for(int i=2; i<50000; i++) { if(!boo[i]) p[k++]=i; for(int j=0; j<k&&i*p[j]<50000; j++) { // cout<<i*p[j]<<endl; boo[i*p[j]]=1; if(!(i%p[j])) break; } } }//筛选法打表 int phi(int n) { int rea=n; for(int i=0; p[i]*p[i]<=n; i++)//对于一些不是素数的可不遍历 if(n%p[i]==0) { rea=rea-rea/p[i]; while(n%p[i]==0){ n=n/p[i]; } } if(n>1) rea=rea-rea/n; return rea; }
3）递推求欧拉函数
如果频繁的使用欧拉函数值，就需要预先打表，下面介绍递推求欧拉公式的方法。
可预先之所有数的欧拉函数值都为她本身，有定理可知，如果p是一个正整数且满足φ（p）=p-1;那么p是素数，在遍历过程中如果遇到欧拉函数与自身相等的情况。那么说明该数为素数，把这个数的欧拉函数值改变，同时也把能被素因子整除的数改变。
//3.递推 int pp[20000]; for(int i=1; i<=maxn; i++) pp[i]=i; for(int i=2; i<=maxn; i+=2) pp[i]/=2; for(int i=3; i<=maxn; i+=2) if(pp[i]==i) for(int j=i; j<=maxn; j+=i) pp[j]=pp[j]/i*(i-1);