欧拉函数的计算方法

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;
}

我看到了上面的Euler phi函数实现，它是O(sqrt n)级别的。我不理解为什么在for循环中要使用i*i<=n和改变n的原因。据说可以在远小于O(sqrt n)的时间内完成。如何实现呢？链接（俄语）

- DCoder

Answer 1

i*i<=n与i<=sqrt(n)相同，从而您的迭代只持续到sqrt(n)的顺序。

使用欧拉函数的直接定义，您应该找到能够被n整除的质数。

- Santosh Linkha

Answer 2

这个函数是通过试除法实现整数分解的简单实现，但不同于在找到因子时报告它们，该函数使用因子来计算phi。通过使用更好的算法查找因子，可以在小于O(sqrt n)的时间内计算phi；最佳方法取决于n的大小。

- user448810

---

什么是更好的找因子算法？请提及该算法的名称。 - DCoder

Rho算法和p-1算法、SQUFOF、连分数、椭圆曲线算法、二次筛法、数域筛法等等，这里只是举几个例子。请注意，其中一些只有在专家的手中才能发挥出良好的效果。 - user448810

@DCoder，为什么不按照你引用的页面上在“可以比O(sqrt(n))更快地找到phi”的陈述后面的链接呢？那个链接回答了这个问题，这应该不会让人感到惊讶，因为它还提到了“用于分解的高效算法”。它描述了像Pollard rho分解这样的东西，可以在20位以上的数字中击败试除法。我不明白你怎么能阅读那个页面而不愿意跟随其中的链接。 - Douglas Zare

Answer 3

如果你想要求欧拉函数的最大值（称为N），并且N足够小，以至于你可以在内存中拥有大小为N的表格，那么你可以在每次计算时更好地优化，代价是在任何计算之前都必须建立一个表格。

一种方法是先构建质数表，然后使用每个质数最多sqrt(n)来进行试除法，而不是使用每个整数最多sqrt(n)来进行试除法。

你可以通过构建一个表格来改进这个方法，该表格为每个整数2..N给出最小的质数因子。通常的Sieve of Eratosthenes可以简单修改用于构建这样的表格。然后计算一个数字的欧拉函数时，你可以使用该表格找到最小的质数因子（并将其累加到答案中），然后将该数字除以表格条目，使用表格找到最小的质数来除以它，依此类推。

- dmuir