欧拉计划第3题：大整数最大质因数求解代码无输出问题排查

问题根源 #

1. 遍历范围过大导致程序长期无响应
   你的findFactors函数通过从1遍历到目标数num来寻找所有因数，对于600851475143这种12位的大数，这个循环需要执行数百亿次，程序会陷入极长时间的计算，并非无输出无报错，而是还在后台运行。

2. 逻辑错误：混淆因数与质因数
   代码直接将所有因数当作质因数处理，但题目要求的是质因数（即能整除目标数的质数），而非所有因数。

高效解决方案 #

使用质因数分解的优化算法，大幅减少计算量：

def largest_prime_factor(num: int) -> int:
    max_prime = -1
    # 先处理所有2的因子
    while num % 2 == 0:
        max_prime = 2
        num = num // 2
    # 处理奇数因子，遍历到num的平方根即可
    i = 3
    while i * i <= num:
        # 除尽当前因子i
        while num % i == 0:
            max_prime = i
            num = num // i
        i += 2
    # 若剩余num是大于2的质数，直接作为最大质因数
    if num > 2:
        max_prime = num
    return max_prime

target_num = 600851475143
result = largest_prime_factor(target_num)
print(f"The largest prime factor of {target_num} is {result}")

代码说明 #

• 优先处理所有2的因子，将目标数快速缩小为奇数，减少后续循环次数
• 仅遍历到目标数的平方根：若一个数有大于其平方根的因子，对应的另一个因子必然小于平方根，已被提前处理
• 每次找到因子后，将目标数除以该因子直到无法整除，确保处理的是质因数
• 最后剩余的大于2的数本身就是质数，直接作为最大质因数

运行上述代码，无论是测试数13195还是目标数600851475143，都能快速得到正确结果。

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