博客

欧拉函数（Euler’s totient function）又称为欧拉φ函数（Euler’s phi function），其定义为小于等于 n 的正整数中与 n 互质的数的个数。欧拉函数通常用符号 φ(n) 表示，其中 n 是一个正整数。

欧拉函数的计算公式如下：

φ(n) = n * (1 – 1/p1) * (1 – 1/p2) * … * (1 – 1/pk)

其中，p1,p2,…,pk 为n的不同的质因数。

下面介绍如何使用Python计算欧拉函数。

方法一：直接暴力枚举

可以直接枚举小于等于n的所有正整数，用gcd函数来判断是否与它互质，最后统计数量即可：

# 计算欧拉函数phi(n)
import math

def phi(n):
    res = 1
    for i in range(2, n+1):
        if math.gcd(i, n) == 1:
            res += 1
    return res

方法二：质因数分解

欧拉函数可以利用质因数分解的方法计算，先把n分解质因数，然后利用欧拉函数的公式计算即可。

# 计算欧拉函数phi(n)
import math

def phi(n):
    res = n
    if n == 1:
        return 1
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            res -= res // i
            while n % i == 0:
                n //= i
    if n > 1:
        res -= res // n
    return res

两种方法的时间复杂度都是 O(nlogn)，但第二种方法更快一些。

以上就是 Python 算法常见计算欧拉函数的完整攻略，希望能对您有所帮助。