欧拉计划 #23 优化

Question

金额不多

如果一个数 n 的真约数之和超过 n，则称它为丰数。求所有不能写成两个大数之和的正整数之和。

我已经尝试了几种方法，并以我有限的编码知识尽可能地优化了我的代码。几天前我开始学习如何编码，我发现了这个页面，（欧拉项目），我从学习中偏离了一点，只是开始编码来尝试解决问题。到目前为止，我已经成功地解决了大部分最简单的问题而没有花费很长时间，但相比之下，这个问题花费的时间太长了。抱歉，如果我的代码无法理解。

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)

（"abundant" 是一个包含所有丰富数字的列表。）这不是整个代码，只是我认为花费大部分时间的部分。

Answer 1

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

确定 28123 以内所有数字的真约数
Select "abundant" 使用除数列表
找到所有对的丰富数字并标记它们的总和
Select 前面步骤未标记的数字（这些数字将不能表示为两个丰度之和）
计算这个结果的总和

这是一个例子：

# 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))

欧拉计划 #23 优化

Project Euler #23 Optimization

python

number-theory