不使用线程/进程优化Python欧拉项目最大质因数求解代码

问题背景 #

正在解决欧拉项目的最大质因数问题，采用暴力法实现，项目包含prime.py和app.py两个文件。当前代码运行效率极低，每1000000次循环约耗时5秒，针对目标数600851475143预估总运行时长超13.9小时，且后续循环会更慢。希望在不使用线程/进程的前提下，通过简单代码优化提升效率，暂不考虑更优的数学解法，仅从代码层面学习优化思路。

当前实现代码 #

prime.py #

import math


def is_prime_number(number):
    if number % 2 == 0:
        return False
    root_of_number = math.ceil(math.sqrt(number))
    for i in range(3, root_of_number + 1, 2):
        if number % i == 0:
            return False
    return True

app.py #

# The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?

from prime import is_prime_number

def main():
    number = int(input("Please enter an integer: "))
    largest_prime_factor = 0

    for i in range(1, number + 1):
        if is_prime_number(i):
            if number % i == 0:
                if i > largest_prime_factor:
                    largest_prime_factor = i
        if i % 1000000 == 0:
            print(i)
    print(f"Largest prime factor of {number}: {largest_prime_factor}")

if __name__ == "__main__":
    main()

代码优化方法 #

1. 修复质数判断函数的逻辑错误 #

原is_prime_number函数无法正确识别2（返回False）和1（返回True），这会导致结果错误并增加无效计算。修改后补充边界条件，同时用更高效的整数平方根计算：

import math

def is_prime_number(number):
    # 小于2的数都不是质数
    if number <= 1:
        return False
    # 2是唯一的偶质数
    if number == 2:
        return True
    # 偶数直接排除
    if number % 2 == 0:
        return False
    # 用整数平方根替代sqrt+ceil，更高效准确
    root_of_number = math.isqrt(number)
    # 仅遍历奇数到平方根
    for i in range(3, root_of_number + 1, 2):
        if number % i == 0:
            return False
    return True

2. 调换判断顺序，减少质数判断调用次数 #

原代码先判断i是否为质数，再判断是否是目标数的因数。但大部分数都不是目标数的因数，先判断number % i == 0，再判断是否为质数，能大幅减少耗时的质数判断操作：

# 修改main函数中的循环逻辑
for i in range(1, number + 1):
    if number % i == 0:  # 先判断是否是因数
        if is_prime_number(i):  # 再判断是否是质数
            if i > largest_prime_factor:
                largest_prime_factor = i
    if i % 1000000 == 0:
        print(i)

3. 缩小循环范围，避免无效遍历 #

目标数的质因数不会超过其平方根（如果i是大于平方根的质因数，那么number//i必然是小于平方根的因数），因此循环只需遍历到sqrt(number)即可，同时同步检查number//i是否为质数，循环次数直接从数十亿级降到百万级：

import math
from prime import is_prime_number

def main():
    number = int(input("Please enter an integer: "))
    largest_prime_factor = 0
    sqrt_num = math.isqrt(number)

    # 单独处理2的情况，避免循环中重复判断
    if number % 2 == 0:
        largest_prime_factor = 2
        # 移除所有2的因数（可选，进一步减少后续计算）
        current = number // 2
        while current % 2 == 0:
            current = current // 2

    # 仅遍历奇数到平方根
    for i in range(3, sqrt_num + 1, 2):
        if number % i == 0:
            if is_prime_number(i):
                if i > largest_prime_factor:
                    largest_prime_factor = i
            # 检查对应的另一因数是否为质数
            counterpart = number // i
            if counterpart != i and is_prime_number(counterpart):
                if counterpart > largest_prime_factor:
                    largest_prime_factor = counterpart
        if i % 100000 == 0:  # 调整进度打印频率
            print(f"Processed up to: {i}")
    
    # 特殊情况：目标数本身是质数
    if is_prime_number(number):
        largest_prime_factor = number
    
    print(f"Largest prime factor of {number}: {largest_prime_factor}")

4. 局部变量提升访问速度 #

Python中局部变量的访问速度比全局变量快，把频繁调用的函数和变量转为局部变量：

def main():
    number = int(input("Please enter an integer: "))
    largest_prime_factor = 0
    # 将is_prime_number转为局部变量，提升访问效率
    is_prime = is_prime_number
    sqrt_num = math.isqrt(number)

    # 后续逻辑同上...

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