Project Euler第23题Python代码优化求助：运行速度过慢

你的问题确实出在最后那层嵌套循环——每次遍历每个数都要逐个检查盈数，这会带来大量重复计算，拖慢整体速度。咱们一步步来优化，从因数和计算到最后求和，都能找到提升效率的点：

1. 先优化真因数和的计算：用筛法替代逐个遍历 #

你当前计算每个数的真因数和时，是逐个数字遍历它的因数，这种方法对于大数来说效率不高。我们可以用类似埃拉托斯特尼筛法的思路反向操作：遍历每个因数，把它加到所有倍数的因数和里。这样一次遍历就能算出所有数的真因数和，速度会快很多。

示例代码：

max_num = 28123  # 题目明确给出的上限，比你用的20162更准确
divisor_sum = [1] * (max_num + 1)  # 初始化每个数的因数和至少为1

for i in range(2, max_num + 1):
    for j in range(i * 2, max_num + 1, i):
        divisor_sum[j] += i

这样divisor_sum[n]就是n的所有真因数之和，比逐个计算高效得多。

2. 快速筛选出所有盈数 #

有了因数和数组，筛选盈数就变得非常简单：

abundant = [n for n in range(12, max_num + 1) if divisor_sum[n] > n]

直接生成所有大于12的盈数（因为12是最小的盈数）。

3. 高效生成所有可表示为两个盈数之和的数 #

这里不用逐个检查每个数是否能被表示，而是直接生成所有可能的两个盈数之和，然后用布尔数组标记这些数。这种方式能避免大量重复判断：

can_be_expressed = [False] * (max_num + 1)

for i in range(len(abundant)):
    a = abundant[i]
    for j in range(i, len(abundant)):
        total = a + abundant[j]
        if total > max_num:
            break  # 超过上限就停止后续计算
        can_be_expressed[total] = True

这里从i开始遍历第二个盈数，避免重复计算a+b和b+a的情况，一旦和超过上限就break，进一步减少不必要的运算。

4. 计算最终结果 #

最后，把所有不能被表示为两个盈数之和的数加起来即可：

result = sum(n for n in range(1, max_num + 1) if not can_be_expressed[n])
print(result)

为什么你的原代码慢？ #

你原代码里的内层循环for k in abundant会遍历所有盈数，即使i - k已经小于最小的盈数（12），还是会继续遍历一部分内容。而用布尔数组标记的方式，一次性生成所有可能的和，后续求和时只需要遍历一次数组，时间复杂度从O(N*M)（N是总数，M是盈数个数）降到了O(M²)，但M远小于N，所以整体速度会提升非常明显。

另外，你原代码里用了numbers.difference(tot)，但numbers是列表，并没有difference方法——这个小问题在优化后的代码里也自然解决了。

完整优化代码 #

max_num = 28123

# 计算每个数的真因数和
divisor_sum = [1] * (max_num + 1)
for i in range(2, max_num + 1):
    for j in range(i * 2, max_num + 1, i):
        divisor_sum[j] += i

# 筛选所有盈数
abundant = [n for n in range(12, max_num + 1) if divisor_sum[n] > n]

# 标记所有可表示为两个盈数之和的数
can_be_expressed = [False] * (max_num + 1)
for i in range(len(abundant)):
    a = abundant[i]
    for j in range(i, len(abundant)):
        total = a + abundant[j]
        if total > max_num:
            break
        can_be_expressed[total] = True

# 计算结果
result = sum(n for n in range(1, max_num + 1) if not can_be_expressed[n])
print(result)

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