Python遍历整数区间时意外陷入无限循环问题求助

你编写的代码尝试寻找600851475143的最大质因数，但因算法效率过低导致循环无法在合理时间内结束，最终看不到print(max(primes))的输出。原代码存在两个核心效率问题：

• 遍历范围过大：原循环range(2, c)要遍历到600851475143，这个量级的循环完全无法在短时间内完成。
• 质数判断低效：prime_x函数遍历从2到n的所有数判断质数，实际只需遍历到sqrt(n)即可——若n存在大于其平方根的因数，必然对应一个小于平方根的因数，无需全部遍历。

优化方案1：改进质数判断+缩小遍历范围 #

import math

def prime_x(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    # 仅遍历奇数至n的平方根，大幅减少判断次数
    for x in range(3, int(math.isqrt(n)) + 1, 2):
        if n % x == 0:
            return False
    return True

c = 600851475143
max_prime = 0

# 遍历范围缩小至sqrt(c)，超过该范围的因数仅可能是c本身（当c为质数时）
for num in range(2, int(math.isqrt(c)) + 1):
    if prime_x(num) and c % num == 0:
        max_prime = num
        # 持续除以该质因数，缩小后续遍历的目标值
        while c % num == 0:
            c = c // num

# 若剩余c大于1，说明其本身就是质数，即最大质因数
if c > 1:
    max_prime = c

print(max_prime)

优化方案2：直接质因数分解（无需单独判断质数） #

这是更高效的思路——不需要先判断质数，直接通过分解目标数来找到质因数：

import math

c = 600851475143
max_prime = 0

# 先处理所有2的因数
while c % 2 == 0:
    max_prime = 2
    c = c // 2

# 仅处理奇数因数，从3开始每次加2，遍历至sqrt(c)
for num in range(3, int(math.isqrt(c)) + 1, 2):
    # 若num能整除c，持续除以num直到无法整除，此时num必然是质因数
    while c % num == 0:
        max_prime = num
        c = c // num

# 剩余的c若大于2，即为最大质因数
if c > 2:
    max_prime = c

print(max_prime)

关于原代码加print能看到结果的原因 #

你在循环内加print能看到输出，是因为每次找到质因数就会打印，但循环本身仍在持续遍历至600851475143——这个过程耗时极长，永远无法在合理时间内完成，因此你看不到循环结束后的print(max(primes))输出。

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