C++ 中的欧拉函数

Question

谁能解释一下，这个欧拉函数是什么意思：

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

我试图制定一个标准路径来解决这个任务，但它已经超过了时间限制。我找到了欧拉函数的这个解释，但是我看不懂。为什么我们要迭代 i*i<n 而不是 i<n，while 循环中发生了什么等等。我知道我们可以将欧拉函数写成 f(n) = n * (1-1/p1)(1-1/p2)...(1-1/pk)，其中 pi 是质数，但我不明白这段代码是如何工作的。

Answer 1

我们这样迭代是为了提高时间性能，因为一个数的所有质因数都等于或小于该数的平方根（如果一个数不满足这个数，那么它就是一个质数）。然后，当我们找到数字的质因数时，我们将数字 n 除以该因数，直到我们无法再除以它，因此我们从数字中提取质因数。

Answer 2

r*(1-1/p<sub>k</sub>) = r - r/p<sub>k</sub>

这正是 result -= result/i 所做的。 result 是到目前为止的乘积，i 是下一个素数。