欧拉 Phi 函数实现背后的理论

Question

我在 topcoder 上找到了 euler 的 phi 函数的实现。代码如下：

int fi(int n) {          
    int result = n;          
    for(int i=2;i*i <= n;i++) {            
        if (n % i == 0) result -= result / i;            
           while (n % i == 0) n /= i;          
    }          
    if (n > 1) result -= result / n;          
    return result;        
}

我想知道这个实现背后的确切理论。我的理解是，如果我得到一个除以 n 的整数，那么我将从结果中减去 result/i（我不知道为什么）。然后代码将 n 除以 i 直到它可以整除。我不明白的是代码的最后一部分。

if(n > 1) result -= result / n;

我所知道的是，如果现阶段n大于1，那么n就是质数。我想知道，到目前为止我对这段代码的理解是否正确以及这段代码背后的确切理论。

Answer 1

查找欧拉总函数。

如果一个数n被分解成素数的乘积，那么

phi(p1^m1*...*pk^mk) = (p1-1)*p1^(m1-1)*...*(pk-1)*pk^(mk-1)

算法忠实地计算。

是可逆的余数类modn的个数。它是费马扩展小定理的指数，if gcd(a,n)=1 then

a ^ b == a ^ (b mod phi(n))  mod n

迭代按升序查找输入 n 的素因子。如果 p 被发现为质因数，则 result = k*p^m 其中 m 也是输入中 p 的重数。操作 result -= result/p 的结果是

result = k*p^m - k*p^(m-1) = k*(p-1)*p^(m-1).

你是对的，迭代后n>1当最大素因子具有多重性m=1时，并且在totient值中这个因子减少1。

欧拉 Phi 函数实现背后的理论

Theory Behind Euler's Phi Function's Implemention

math

theory