直接单独求解
φ(n) = n * (1-1/p1) * (1-1/p2)....(1-1/pk)，其中 p1、p2…pk 为 n 的所有素因子。
比如：φ(12) = 12 * (1-1/2) * (1-1/3) = 4。
int euler(int x) { int rs=x,a=x; for(int i=2; i*i<=a; i++) if(a%i==0) // 最开始先 a%i == 0 进去马上执行 rs 操作，是因为确保了 i 肯定是素数 { rs=rs/i*(i-1); // 先进行除法是为了防止中间数据的溢出 while(a%i==0) a/=i; // 确保下一个 i 是素数 } if(a>1) rs=rs/a*(a-1); return rs; }
筛法欧拉函数
在“直接单独求解”思想的基础上，可以用类似求素数的筛法。
先筛出 n 以内的所有素数，再以素数筛每个数的 φ 值。
比如：求 10 以内所有数的 φ 值：
设一数组 phi[11]，赋初值 phi[1]=1,phi[2]=2...phi[10]=10；
然后从 2 开始循环，把 2 的倍数的 φ 值 *(1-1/2)，则 phi[2]=2*1/2=1, phi[4]=4*1/2=2, phi[6]=6*1/2=3....；
再是 3，3 的倍数的 φ 值 *(1-1/3)，则 phi[3]=3*2/3=2, phi[6]=3*2/3=2, phi[9]=.....；
再5，再7...因为对每个素数都进行如此操作，因此任何一个 n 都得到了 φ(n) = n * (1-1/p1) * (1-1/p2)....(1-1/pk) 的运算。
const int maxn=100; int phi[maxn+5]; void euler() { for(int i=1;i<=maxn;i++) phi[i]=i; for(int i=2;i<=maxn;i+=2) phi[i]/=2; for(int i=3;i<=maxn;i+=2) if(phi[i]==i) // 保证了此时的 i 一定是第一次使用，避免重复 *(1-1/pi) for(int j=i;j<maxn;j+=i) phi[j]=phi[j]/i*(i-1); // 先进行除法是为了防止中间数据的溢出 }
