项目Euler问题#23 (非充分和)

Question

欧拉项目问题23

完全数是指它的适当除数之和与其数完全相等的一个数。例如，适当的除数之和为\$28 \$ 1 +2+4+7+ 14 = 28\$，这意味着\$28\$是一个完美的数字。如果一个数的适当除数之和小于n\n，则称为亏数；如果这个数超过n\n，则称它为富足数。由于12是最小的丰富数，\1+2+3+4+6=16，可以写成两个富足数之和的最小数是\24。通过数学分析，可以证明所有大于28123的整数都可以写成两个丰富数的和。然而，这个上限不能通过分析进一步降低，即使已知不能表示为两个丰富数之和的最大数小于这个极限。找出所有正整数的和，这些正整数不能写成两个丰富数的和。

我没有编程背景。我编写的代码是在测试我的耐心，并没有给出任何解决方案。请提供优化的建议。

array = []
array1 =[] 
for i in range(12, 28123):
add = 0
for j in range(1, i//2 + 1):
        if i%j ==0:
           add += j
        if add > i:
           array.append(i)
           break
total_num = list(range(1,28124))

for k in range(len(array)):
    for l in range(k, len(array)):
        add = 0
        add = array[k] + array[l]
        if add not in array1 and add in total_num:
            array1.append(add)
        else:
            continue

print(sum(total_num)-sum(array1))

Answer 1

我假设您最初的程序如下(因为问题中没有适当的缩进)：

array = []
array1 =[]
for i in range(12, 28123):
    add = 0
    for j in range(1, i//2 + 1):
        if i%j ==0:
            add += j
        if add > i:
            array.append(i)
            break
total_num = list(range(1,28124))

for k in range(len(array)):
    for l in range(k, len(array)):
        add = 0
        add = array[k] + array[l]
        if add not in array1 and add in total_num:
            array1.append(add)
        else:
            continue

print(sum(total_num)-sum(array1))

首先，干得好！我不认为您的实现有任何逻辑问题。

小淘气

通常，最好避免使用像array和array1这样的名称。这与性能无关，但对程序可读性有很大帮助。在本例中，array和array1的更好名称是abundants和abundant_sums。

性能

乍一看，可以很容易地解决两个主要的性能问题：

if add not in abundant_sums and add in total_num

这是两个数组查找，它们需要线性时间(O(n))，并对每一对可能的丰富数字执行(结果是超过4800万次！)。

让我们分别讨论这两个问题：

• add not in abundants --完全删除它的方法是使abundant_sums成为一个设置，而不是一个数组。这样，您就可以直接说abundant_sums.add(add)，而不必首先检查它是否已经存在(好的，也许应该调用add以避免这样的情况:)
• add in total_num -这基本上只是一个范围检查。实际上，只是一个上限的检查，因为你处理的数字永远不会产生小于24的和。因此，与遍历28+K项数组的28+K不同，您可以简单地说是add <= 28123。就这样。

通过应用这两种优化，我得到了一个程序，该程序在略高于30的时间内产生正确的结果：

abundants = []
abundant_sums = set()
for i in range(12, 28123):
    add = 0
    for j in range(1, i//2 + 1):
        if i%j ==0:
            add += j
        if add > i:
            abundants.append(i)
            break
print len(abundants)
total_num = list(range(1,28124))

for k in range(len(abundants)):
    for l in range(k, len(abundants)):
        add = 0
        add = abundants[k] + abundants[l]
        if add <= 28123:
            abundant_sums.add(add)
print(sum(total_num)-sum(abundant_sums))

您可以执行的另一个轻微的优化是不计算total_num的和，而只是使用公式max * (max+1) / 2。但是，在您的情况下，这不太可能带来很大的好处，因为这种计算只进行一次。不管怎么说，我相信知道这个技巧是很好的。