欧拉phi函数的计算

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) 如何？ link (in Russian)

Answer 1

i*i<=n 与 i<= sqrt(n) 相同，您的迭代仅持续到 sqrt(n).

的顺序

使用 Euler totient function 的直接定义，您应该找到整除 n 的质数。

Answer 2

该函数是通过试验除法进行整数分解的直接实现，不同之处在于它不是在找到因子时报告因子，而是使用因子来计算 phi。通过使用更好的算法来查找因子，可以在小于 O(sqrt n) 的时间内完成 phi 的计算；最好的方法取决于 n.

的大小

Answer 3

如果你想要的最大数字（N 说）足够小，你可以在内存中有一个 table 大小的 N，那么你可以做得更好，根据评估，以必须在任何评估之前构建 table 为代价。

一种方法是先构建一个 table 个素数，然后不使用最多 sqrt(n) 的每个整数进行试除，而是使用最多 sqrt(n) 的每个素数进行试除.

您可以通过构建 table 素数而不是 table 来改进这一点，该 table 给出（对于每个整数 2..N）整除该数的最小素数。可以使用通常的 Sieve of Eratosthenes 的简单修改来构建这样的 table。然后计算一个数字的总和，你使用 table 找到除以该数字的最小素数（并将其累加到你的答案中），然后将数字除以 table 条目，使用 table 找到整除它的最小素数，依此类推。

欧拉phi函数的计算

Calculation of euler phi function

algorithm

math

implementation