Euler #23优化[Python3.6]

Question

我很难让我的代码快速运行，因为Project问题23。以下是问题所在：

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

我的密码是：

import math
import bisect
numbers = list(range(1, 20162))
tot = set()
numberabundance = []
abundant = []
for n in numbers:
    m = 2
    divisorsum = 1
    while m <= math.sqrt(n):
        if n % m == 0:
            divisorsum += m + (n / m)
        m += 1
    if math.sqrt(n) % 1 == 0:
        divisorsum -= math.sqrt(n)
    if divisorsum > n:
        numberabundance.append(1)
    else:
        numberabundance.append(0)
temp = 1
# print(numberabundance)
for each in numberabundance:
    if each == 1:
        abundant.append(temp)
    temp += 1
abundant_set = set(abundant)
print(abundant_set)
for i in range(12, 20162):
    for k in abundant:
        if i - k in abundant_set:
            tot.add(i)
            break
        elif i - k < i / 2:
            break
print(sum(numbers.difference(tot)))

我知道问题在底部的for循环中，但我不知道如何解决它。我在这里看到的其他一些答案之后，我试着对它建模，但它们似乎都没有用。有什么建议吗？谢谢。

Answer 1

你的上限是不正确的-这个问题是all integers greater than 28123 can be written ...，而不是20162。

更改绑定后，生成的abundant是正确的，尽管您可以通过直接添加到集合abundant来实现这一生成，而不是创建位掩码数组numberabundance。

最后一个循环也是不正确的--根据问题，您必须

求所有正整数的和

而你的代码

for i in range(12, 20162):

将跳过12以下的数字，也不包括正确的上限。

我有点困惑于你的选择

elif i - k < i / 2:

由于丰度已经被排序，我只想检查内环是否通过了外部循环的中点：

if k > i / 2:

另外，由于我们只需要这些数字的sum，我只需要保持一个运行的总数，而不必对一个集合做最后的和。

下面是进行上述更改后的结果：

import math
import bisect
numbers = list(range(1, 28123))
abundant = set()

for n in numbers:
    m = 2
    divisorsum = 1
    while m <= math.sqrt(n):
        if n % m == 0:
            divisorsum += m + (n / m)
        m += 1
    if math.sqrt(n) % 1 == 0:
        divisorsum -= math.sqrt(n)
    if divisorsum > n:
        abundant.add(n)
#print(sorted(abundant))
nonabundantsum = 0
for i in numbers:
    issumoftwoabundants = False
    for k in abundant:
        if k > i / 2:
            break

        if i - k in abundant:
            issumoftwoabundants = True
            break

    if not issumoftwoabundants:
        nonabundantsum += i

print(nonabundantsum)

这里的例子