项目Euler＃23优化

Question

不丰富的总和

问题23

如果其适当的除数的总和超过n，则称为数字n。找到所有无法写入两个大量数字的总体整数的总和。

我尝试了几件事，并尽可能多地优化了我的代码。几天前，我开始学习如何编码，发现此页面(Project Euler(，我偏离了学习，并开始编码以尝试解决问题。到目前为止，我已经设法解决了大多数最简单的问题而没有花费很长时间，但是相比之下，这个问题花费的时间太长了。抱歉，如果我的代码无法理解。

sum_abundant = []
for i in abundant:
    for n in abundant:
        c = i + n
        if n > i:
            break
        if c < 28123:
            if c not in sum_abundant:  # if the number has already been removed, it won't remove it again.
                sum_abundant.append(c)

("丰富"是所有丰富数字的列表。(这不是整个代码，只是我认为大部分时间都需要的部分。

Answer 1

您可以采用的一种方法是将问题分解为中间步骤：

• 确定最多28123的所有数字的适当分配
• 使用除数列表选择"丰富"的数字
• 找到所有的大量数字并标记它们的总和
• 选择前一步未标记的数字(这些数字将是不能表示为两个丰富的总和的数字(
• 计算此结果的总和

这是一个示例：

# Create a list of proper divisora for all numbers up to 28123...
properDivs     = [ [] for _ in range(28124) ] 
for n in range(1,28124):
    for i in range(2*n,28124,n):
        properDivs[i].append(n)
# Select the numbers that are abundant (sum of divisors > number itself)...
abundants = [n for n,divs in enumerate(properDivs) if sum(divs)>n]
# Find all pairs of abundant numbers and flag their sums
from itertools import combinations_with_replacement
sumOf2Abundants = [False for _ in range(28124)]
for a,b in combinations_with_replacement(abundants,2):
    if a+b<len(sumOf2Abundants):
        sumOf2Abundants[a+b] = True
# Select numbers that were not flagged...
result = [n for n,isSumOf2 in enumerate(sumOf2Abundants) if not isSumOf2]
# compute and print the sum of the above result
print(sum(result))