欧拉问题3求解代码的异常输出及原理、性能疑问

1. 为何6859的输出异常？ #

6859是19³，代码的问题出在两个地方：

• 循环条件错误：外层循环用了i * i < n，当n被两次除以19后变为19时，19*19=361并不小于19，外层循环直接终止，没机会处理最后一个19的整除操作；继续执行内层循环后，n被第三次除以19变为1，此时循环彻底结束。
• 未判断剩余n的合法性：代码最后直接把int(n)加入列表，但1不是质数，导致错误追加了1。

修正方案：把外层循环条件改为i * i <= n，并且在最后追加n前，判断n > 1（只有大于1的数才是质因数）。

2. 该代码为何仅输出质因数？ #

代码的核心逻辑是试除法分解质因数：

• 从i=2开始试除，若i能整除n，说明i是n的质因数（因为如果i是合数，它的质因数已经被之前的循环处理过，此时n已无法被这些质因数整除，所以i不可能是合数）；
• 每次整除成功就将i加入列表，并把n更新为n/i，缩小后续处理范围；
• 整个过程只收集能整除n的质数因子，没有处理非质因数的逻辑，因此只会输出质因数。

3. 该代码为何运行速度远快于其他解法？ #

这是优化后的试除法，优势在于：

• 遍历范围缩小到√n：如果n有大于√n的因子，对应的另一个因子必然小于√n，已经被处理过，无需遍历到n本身，大幅减少循环次数；
• 动态缩小n的范围：每次找到质因数后立即更新n，后续循环只需要处理更小的数字，避免重复计算；
• 无冗余预处理：不需要预先生成质数列表（如埃氏筛），而是在试除过程中自然筛选出质因数，省去了生成质数的时间和空间开销。

对比低效解法（如从2到n逐个判断因子、预先生成大量质数），该方法时间复杂度更低，因此运行更快。

修正后的代码示例 #

n = 6859
i = 2
b = []
while i * i <= n:
    while n % i == 0:
        n = n // i  # 用整数除法避免浮点数精度问题
        b.append(i)
    i += 1
if n > 1:
    b.append(n)

print(n)
print(b)

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