欧拉公式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) {	//注1
		if(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;	//注3
    return n;
}

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

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

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

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