如何在Python中高效计算给定范围内所有数的约数和？

当前方案的问题 #

你当前的代码采用逐个计算单个数约数和的思路，核心逻辑是对每个数遍历其平方根以内的数找约数，再累加结果。这种方案的问题在于：

• 时间复杂度为O(n√n)，当n达到1e5时，总操作量约为3e7；n到1e6时，操作量会飙升到1e9级别，性能急剧下降
• 存在大量重复计算：比如约数2会被所有偶数重复检查，浪费计算资源

优化方案：倍数累加筛法 #

换一种思路：反过来遍历约数，给所有倍数的约数和累加当前约数。这种方法类似埃拉托斯特尼筛法，时间复杂度为O(n log n)，性能提升几个数量级。

优化后代码 #

def compute_divisor_sums(max_num):
    # 初始化数组，每个位置对应数字的约数和，初始为0
    divisor_sums = [0] * (max_num + 1)
    # 遍历每个可能的约数d
    for d in range(1, max_num + 1):
        # 给d的所有倍数（d, 2d, 3d...）的约数和加上d
        for multiple in range(d, max_num + 1, d):
            divisor_sums[multiple] += d
    return divisor_sums

# 计算0到999999的所有数的约数和
result = compute_divisor_sums(999999)
print(result)

方案优势 #

1. 效率极高：对于n=1e6，总操作量约为1e6*(ln1e6 + γ)≈1e6*14≈1.4e7，比原方案的1e9操作量快近100倍
2. 逻辑简洁：无需处理平方根、平方数判断等复杂逻辑，代码更易维护
3. 结果准确：自动处理了0（约数和为0）、1（约数和为1）等特殊情况，原代码中divSum(0)返回1是错误的，优化后的代码修正了这个问题

额外细节说明 #

• 如果只需要计算正整数的约数和，逻辑完全一致，无需调整
• 若内存紧张（比如计算到1e8级别），可以考虑分块处理，但对于1e6的范围，直接初始化数组完全没问题

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