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 而不是 i，while 循环中发生了什么等等。我知道我们可以将欧拉函数写为 f(n) = n * (1-1/p1)(1-1/p2)...(1-1/pk)，其中 < code>pi 是一个素数，但我不明白这段代码是如何工作的。

Answer 1

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

Answer 2

r*(1-1/pk) = r - r/pk

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

Answer 3

您必须确保 pi 是 n 的质因数，而不仅仅是小于 n 的任何质数。