欧拉函数 (φ 函数) 求解方法详解 - 3 种常见算法

欧拉函数 (φ 函数) 求解方法详解 - 3 种常见算法

欧拉函数 (φ 函数) 是数论中一个重要的函数，表示小于或等于 n 的正整数中与 n 互质的数的个数。在这篇文章中，我们将介绍三种常见的求解欧拉函数的方法。

方法一：暴力枚举

最简单的方法是直接枚举小于或等于 n 的正整数，然后对于每个数 i，判断 i 与 n 是否互质。如果互质，则将计数器加 1。这种方法的时间复杂度是 O(n)。

方法二：质因数分解

根据欧拉函数的定义，我们可以将 n 分解质因数，将 n 表示成以下形式：n = p1^k1 * p2^k2 * ... * pm^km，其中 pi 为质数，ki 为正整数。则欧拉函数的值为：φ(n) = (p1-1) * p1^(k1-1) * (p2-1) * p2^(k2-1) * ... * (pm-1) * pm^(km-1)。这种方法的时间复杂度是 O(质因数个数)。

方法三：线性筛法

欧拉函数的一个重要性质是：对于任意正整数 n，有 φ(n) = n * (1-1/p1) * (1-1/p2) * ... * (1-1/pm)，其中 pi 为 n 的质因数。因此，我们可以使用线性筛法预处理出 1~n 的欧拉函数值，时间复杂度为 O(n)。

以上就是三种求解欧拉函数的常见方法。根据具体情况选择合适的方法可以提高计算效率。希望对您有所帮助。