排查Python求解φ(n)=16时代码仅返回17、遗漏其余解的问题

问题原因 #

你当前的代码逻辑是找到第一个满足phi(i) == 16的数值后就会终止循环，所以只会输出最小的符合条件的17，不会继续向后查找其他结果。同时你没有设置合理的搜索边界，无法遍历所有可能的候选值。

调整方案 #

我们可以先设置一个足够覆盖所有候选值的搜索上限（根据欧拉函数的性质，所有满足φ(n)=16的正整数n都小于100，该上限完全足够），遍历范围内所有整数，将符合条件的值存入列表统一输出即可。

调整后的代码如下：

from math import gcd

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

# 搜索上限设置为100，可覆盖所有满足φ(n)=16的正整数
max_search = 100
valid_n = []
for n in range(1, max_search + 1):
    if phi(n) == 16:
        valid_n.append(n)

print("满足φ(n)=16的正整数：", valid_n)

运行结果 #

输出为：
满足φ(n)=16的正整数： [17, 32, 34, 40, 48, 60]

内容的提问来源于stack exchange，提问作者hwanju song