计算某一个数的欧拉函数

欧拉函数（Euler's totient function），也称为φ函数，表示小于等于n的数中与n互质的数的个数。

计算某一个数n的欧拉函数的方法如下：

1. 初始化φ为n。
2. 从2到√n的范围内遍历所有的质数p。
   • 如果n能够整除p，将φ减去φ/p。
   • 继续除以p，直到n无法整除p。
3. 如果n大于1，则说明n本身是一个质数，将φ减去φ/n。
4. 返回φ作为结果。

下面是一个Python示例代码：

import math

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

# 示例测试
print(euler_phi(10))  # 输出4，与10互质的数有1、3、7、9
print(euler_phi(30))  # 输出8，与30互质的数有1、7、11、13、17、19、23、29
``