博客

Python 欧拉函数（Euler’s Totient Function），也称为欧拉phi函数，是指小于等于n的正整数中与n互质的数的个数。通常使用符号φ(n)表示。

下面是欧拉函数的定义：

当n=1时，φ(n)=1；

当n>1时，φ(n)为小于n的所有正整数中与n互质的数的个数。

其中，如果两个自然数a和b的最大公约数为1，则称a与b互质。

欧拉函数是一个非常重要的数学函数，在密码学、计算机科学等领域有广泛的应用。在Python中，有多种方法可以计算欧拉函数。

下面是使用欧拉函数的两个示例代码。

1. 计算欧拉函数

为计算n的欧拉函数φ(n)，可以遍历小于n的各个正整数i，并判断它们与n的最大公约数是否为1，如果是，则将计数器加1，最后返回计数器即可。

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

1. 计算多个数的欧拉函数

如果需要计算多个数的欧拉函数，可以使用如下代码。

from functools import reduce
from math import gcd

def phi(n):
    cnt = 0
    for i in range(1, n+1):
        if gcd(i, n) == 1:
            cnt += 1
    return cnt

def phi_all(numbers):
    return [phi(n) for n in numbers]

numbers = [8, 11, 15, 20]
result = phi_all(numbers)
print(result)

以上示例代码仅供参考，实际应用中建议使用现有的数学库或密码学库，避免出错和提高效率。