欧拉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 (我不知道为什么)，.Then代码除以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)

算法忠实地计算。

是剩余类mod n的数目是可逆的。它是费马推广的小定理的指数，如果是gcd(a,n)=1，则

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时发生，而在现有的值中，这个因子会被1还原。