欧拉计划第23题Python求解结果错误的原因排查

问题背景 #

求解欧拉计划第23题，题目截图如下：

编写Python代码求解时运行结果错误，输出值为395465560，无法定位错误点。

原代码设计逻辑 #

代码分为三个执行步骤：

• 第一步：遍历1到28122区间的整数，计算每个数的真因数和，筛选所有盈数存入列表lst1
• 第二步：双重循环枚举lst1中盈数的两两组合，计算两数之和，将小于等于28123的和存入列表lst2
• 第三步：遍历12到28123区间的整数，将不能表示为两个盈数之和的数存入lst3，最终输出lst3的元素总和

原实现代码 #

lst1 = []
for i in range(1, 28123):
    total = 0
    for j in range(1, i // 2 + 1):
        if i % j == 0:
            total += j
    if total > i:
        lst1.append(i)
lst2 = []
for x in lst1:
    for y in lst1:
        total = x + y
        if total > 28123:
            break
        else:
            lst2.append(total)
lst3 = []
for z in range(12, 28123 + 1):
    if z != lst2:
        lst3.append(z)
print(sum(lst3))

错误点说明 #

1. 核心逻辑错误：成员判断写法完全错误
   代码中判断z是否属于两盈数和的语句为if z != lst2，这是将整数z和整个列表对象做不等比较，判断结果永远为True，直接导致12到28123的所有整数都被加入lst3，最终输出的是这个区间所有整数的总和，和题目要求的计算目标完全不符，这是结果错误的直接原因。
2. 性能问题：存储结构选择错误
   用列表lst2存储两盈数的和会产生大量重复值，后续做成员判断时时间复杂度为O(n)，代码运行速度极慢。应该改用集合存储两盈数的和，既可以自动去重，成员判断的时间复杂度也为O(1)，运行效率会有量级提升。

修正后可运行代码 #

# 筛选所有小于等于28122的盈数
abundant_nums = []
for i in range(1, 28123):
    factor_sum = 0
    for j in range(1, i // 2 + 1):
        if i % j == 0:
            factor_sum += j
    if factor_sum > i:
        abundant_nums.append(i)

# 用集合存储所有<=28123的两盈数和
sum_two_abundant = set()
for x in abundant_nums:
    for y in abundant_nums:
        s = x + y
        if s > 28123:
            break
        sum_two_abundant.add(s)

# 累加所有不能表示为两盈数和的数
result = 0
for num in range(1, 28124):
    if num not in sum_two_abundant:
        result += num

print(result)

运行后可得到正确结果4179871。

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