如何从质因数列表高效计算整数的所有因数？

一、现有方法的优化细节 #

你当前用itertools.product结合质因数频次统计的思路已经是高效方向，但可以从两个点进一步优化：

• 预先生成质因数的幂次集合：比如质因数2出现3次，直接生成[1,2,4,8]，而非通过product生成指数组合后再计算乘积，减少冗余乘法操作。
• 增量式生成因数：不用先凑齐所有幂次组合再计算，而是每处理一个质因数，就对现有因数列表进行扩展。比如初始因数是[1]，处理2时扩展为[1,2,4,8]，再处理3时把每个现有因数乘3并合并，得到[1,2,4,8,3,6,12,24]，最后处理5重复此操作。这种方式内存占用更线性，也减少了批量计算的开销。

二、修改prime_factors函数直接生成因数 #

完全可以在分解质因数的过程中同步生成所有因数，无需先输出完整质因数列表再处理。核心逻辑是：每找到一个质因数及其幂次，就用该质因数的各次幂去扩展当前已有的因数集合。

示例Python代码：

def prime_factors_with_divisors(n):
    divisors = [1]
    # 单独处理质因数2
    count = 0
    while n % 2 == 0:
        count += 1
        n = n // 2
    if count > 0:
        temp = []
        p_power = 1
        for _ in range(count):
            p_power *= 2
            for d in divisors:
                temp.append(d * p_power)
        divisors += temp
    # 处理奇数质因数
    i = 3
    while i * i <= n:
        count = 0
        while n % i == 0:
            count += 1
            n = n // i
        if count > 0:
            temp = []
            p_power = 1
            for _ in range(count):
                p_power *= i
                for d in divisors:
                    temp.append(d * p_power)
            divisors += temp
        i += 2
    # 剩余的n是质数的情况
    if n > 1:
        temp = [d * n for d in divisors]
        divisors += temp
    # 按需排序
    divisors.sort()
    return divisors

调用prime_factors_with_divisors(120)会返回[1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120]，和从质因数列表生成的结果一致。

这种方法的优势：

• 无需额外存储完整质因数列表，节省内存，尤其适合处理大数。
• 分解与因数生成同步进行，省去后续统计、组合计算的步骤，流程更紧凑高效。

三、性能总结 #

• 增量式生成因数的方式，比itertools.product的方案在时间和内存表现上更优，避免了中间组合列表的生成开销。
• 修改后的prime_factors函数直接输出因数，整体链路更短，对于大整数的处理效率提升更明显。

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