欧拉公式C++实现

欧拉函数Euler(n)：求[2,n]中有多少个数与n互素

直接利用公式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn)

其中：

• pi为x的素因数
• 每个素因数只用一次
  • 比如90=2 * 3^2 * 5
    
  • φ(90) = 90 * (1-1/2) * (1-1/3) * (1-1/5)

int Euler(int n) {int ans = n;for(int i = 2; i * i <= n; ++i) { //注1if(n % i == 0) { ans = ans - ans/i; //x(1-1/p1)的变形while(n % i == 0) n /= i; //注2}}if(n != 1) ans = ans - ans/i; //注3return n; }

注1：众所周知，判断因数时不用超过根号n，这跟判断素数的算法是类似的

注2：前面说到了，每个素因数只有一次，但是有的素因数许多很多次幂，比如100=2^2*5^2，此时需要把素因数除尽。

​ 其实，代码的实现原理不是像我们手动计算时，先找出所有的素因数然后代入公式。而是“步步蚕食”，有点类似于φ(90)=φ(2) * φ(45) = φ(9) * φ(5) = 6 * 4 = 24，即先把素因数2消掉，然后把素因数3消掉，最后把素因数5消掉。

注3：因为注1的限制，所以我们有的时候会遇到这样的情况，明明还有素因数没有被消掉，就已经跳出了循环，比如90，当我们消掉3之后，n变成了5，此时就会跳出for循环。所以我们才需要注3，来消掉素因数5。

转载于:https://www.cnblogs.com/huangming-zzz/p/10664381.html

总结

以上是生活随笔为你收集整理的欧拉公式C++实现的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。