Python实现欧拉函数：计算互质正整数个数

欧拉函数，也称为欧拉φ函数（Euler's totient function），是数论中一个重要的函数。它用于计算小于等于给定正整数 n 的所有与 n 互质的正整数的个数。

以下是使用 Python 实现欧拉函数的示例代码：pythondef euler_phi(n): # 初始化互质整数的个数为 n result = n

# 遍历小于等于 n 的所有素数    p = 2    while p * p <= n:        # 如果当前素数是 n 的因子，则更新互质整数的个数        if n % p == 0:            while n % p == 0:                n //= p            result -= result // p        p += 1

# 如果 n 是素数，则更新互质整数的个数    if n > 1:        result -= result // n

return result

代码解析:

初始化: result 初始值为 n，代表初始情况下所有数都与 n 互质。2. 遍历素数: 使用 while 循环遍历小于等于 √n 的所有素数 p。3. 判断因子: 如果 p 是 n 的因子，说明 n 和 p 的倍数都不与 n 互质，需要更新 result。4. 更新结果: 根据欧拉函数的性质，result 每次更新为 result - result // p。5. 处理素数情况: 最后，如果 n 本身是大于1的素数，还需要将 result 减去自身。

**示例：**pythonn = 10result = euler_phi(n)print(f'Euler phi({n}) = {result}')

输出结果：

Euler phi(10) = 4

总结：

上述代码提供了一种简单易懂的欧拉函数计算方法。在实际应用中，如果需要频繁计算欧拉函数值，可以考虑使用更高效的算法，例如预先计算并存储欧拉函数值，以便快速查询。