欧拉函数是小于x的整数中与x互质的数的个数，一般用φ(x)表示。特殊的，φ(1)=1。
若p是质数，显然有φ(p)=p-1。
计算公式：φ(N)=N*(1-1/P1)*(1-1/P2)*...*(1-1/Pn)
单个欧拉函数可以在sqrt(n)计算出来
int euler(int n){ int m=sqrt(n)+1; int ans=n; for(int i=2;i<=m;i++) if(n%i==0){ ans=ans/i*(i-1); while(n%i==0)n/=i; } if(n>1)ans=ans/n*(n-1);//如果n是质数ans=n-1,否则ans不会变 return ans; }
欧拉筛法同时求欧拉函数
void euler(int n) { phi[1]=1; for (int i=2;i<=n;i++) { if (isprime[i]==0) { prime[++num]=i; phi[i]=i-1; } for (int j=1;j<=num&&prime[j]*i<=n;j++){ isprime[i*prime[j]]=1; if (i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } else phi[i*prime[j]]=phi[i]*phi[prime[j]]; } } }
原文：https://www.cnblogs.com/xutianshu/p/10618670.html