c++ - 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/pk) = r - r/pk

这正是这样result -= result/i做的。result是到目前为止的乘积并且i是下一个主要除数。