如何优化10^9范围内多数字的小质因数求解算法？

代码直接优化点 #

• 预计算质数平方：把Primes._primes中每个质数的平方提前计算并存为列表，避免循环内重复执行p**2的幂运算（幂运算比乘法耗时）。例如提前生成prime_squares = [p*p for p in Primes._primes]，循环时直接取对应平方值与n比较。
• 局部变量绑定：将类属性Primes._primes赋值给函数内的局部变量，Python中局部变量的访问速度远快于类属性，能减少属性查找的开销。
• 提前终止循环：每次将n除以质因数后，检查n是否已小于等于300，若是直接跳出循环——因为剩余因数即使大于1也超出我们关注的范围，无需继续分解。
• 位运算优化2的处理：对于质因数2，用n & 1判断奇偶性，n >>= 1代替n //= 2，位运算的执行效率远高于普通算术运算。

算法层面优化 #

• 高频小质数优先处理：将2、3、5这类在Farey分数分子分母中出现频率更高的小质数单独提取出来优先处理，减少后续循环的次数。
• 批量处理思路：如果待分解的数字是批量生成的，可以换一种遍历逻辑——先遍历每个质因数p，再批量处理所有能被p整除的数字，这样能减少重复的循环判断开销。

优化后的示例代码 #

def calc_prime_factors(self, n):
    factors = []
    if n == 1:
        factors.append(1)
        return factors
    
    # 局部变量绑定，提升访问速度
    primes = Primes._primes
    prime_squares = [p * p for p in primes]
    
    # 单独处理2，位运算优化
    if not (n & 1):
        while not (n & 1):
            factors.append(2)
            n >>= 1
        if n <= 300:
            if n > 1:
                factors.append(n)
            return factors
    
    # 处理剩余奇数质数
    for idx, p in enumerate(primes[1:]):
        p_sq = prime_squares[idx + 1]
        if p_sq > n:
            break
        if n % p == 0:
            while n % p == 0:
                factors.append(p)
                n = n // p
            if n <= 300:
                break
    
    if n > 1:
        factors.append(n)
    return factors

额外注意事项 #

• 确认Primes._primes包含了2到300之间的所有质数，避免遗漏导致无效循环或分解不彻底。
• 缓存命中率极低的情况下，直接放弃缓存策略，缓存的读写开销反而会拖慢整体性能。

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