编写一个计算一个正整数n的欧拉函数φ(n)的程序

好的,我很乐意为您编写一个计算正整数n的欧拉函数φ(n)的程序。以下是Python代码实现:

def euler_phi(n):
    result = n
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            while n % i == 0:
                n //= i
            result -= result // i
    if n > 1:
        result -= result // n
    return result

# 测试函数
if __name__ == "__main__":
    n = int(input("请输入一个正整数: "))
    if n > 0:
        print(f"{n}的欧拉函数φ({n})值为: {euler_phi(n)}")
    else:
        print("请输入一个正整数")

这个程序的工作原理如下:

1. 我们定义了一个名为`euler_phi`的函数,它接受一个正整数n作为参数。

2. 初始时,将结果设为n。

3. 我们遍历从2到sqrt(n)的整数。对于每个i,如果i是n的因子:
- 我们不断除以i,直到n不能被i整除。
- 然后从结果中减去结果除以i。

4. 循环结束后,如果n仍然大于1,说明n本身是一个质数,我们需要再从结果中减去结果除以n。

5. 最后返回计算得到的结果。

6. 在主程序中,我们获取用户输入,检查输入是否为正整数,然后调用`euler_phi`函数并输出结果。

这个程序可以有效地计算任何正整数的欧拉函数值。它利用了欧拉函数的一个重要性质:如果p是质数且k >= 1,那么φ(p^k) = p^k - p^(k-1)。