print函数放置位置错误导致持续循环 Project Euler第3题list.append使用问题

核心问题 #

• 循环范围设置不合理：600851475143是6千亿级别的数值，直接遍历到这个数需要执行千万亿次循环，耗时极长，看起来就像程序一直在无限循环
• print语句位置错误：你把print放在for循环的缩进块内，每遍历一个i就会打印一次列表，额外产生了巨量的IO开销，进一步拖慢运行速度
• 变量命名不规范：不要用list作为变量名，这是Python的内置类型名，覆盖之后会导致后续无法正常调用list()方法
• 逻辑不完善：现有代码只会收集所有能整除的因数，不会过滤非质数的因数，也无法得到正确的质因数结果

修复方案 #

1. 优化因数查找逻辑 #

找一个数的因数不需要遍历到数本身，只需要遍历到该数的平方根即可，每次找到因数后直接除尽该因数，就能直接得到质因数，无需额外做质数判断。

2. 调整print语句位置 #

把print放到for循环的外部，等所有循环执行完毕后再打印完整的列表。

修复后可正常运行的参考代码 #

# 求600851475143的最大质因数
import math
target = 600851475143
prime_factors = []

# 先处理偶因数
while target % 2 == 0:
    prime_factors.append(2)
    target = target // 2

# 处理奇因数，步长设为2跳过偶数，只遍历到平方根即可
for i in range(3, int(math.isqrt(target)) + 1, 2):
    while target % i == 0:
        prime_factors.append(i)
        target = target // i

# 剩余值大于2则本身是最后一个质因数
if target > 2:
    prime_factors.append(target)

# 循环结束后打印完整列表
print(prime_factors)
# 取最大质因数直接调用max方法即可
print("最大质因数：", max(prime_factors))

内容的提问来源于stack exchange，提问作者mesut.a