欧拉23项目效率

Question

我试图用python编写一个程序来回答以下问题：

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.
A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.
As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24.
By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis, even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

所以这是我的代码，理论上应该可以工作，但是太慢了。你知道吗

import math
import time

l = 28123

abondant = []
def listNumbers():
        for i in range(1, l):
            s = 0
            for k in range(1, int(i / 2) + 1):
                if i % k == 0:
                    s += k
            if s > i:
                abondant.append(i)

def check(nb):
    for a in abondant:
        for b in abondant:
            if a + b == nb:
                return False
    return True

def main():
    abondant_sum = 0
    for i in range(12, l):
        if check(i):
            abondant_sum += i
    return abondant_sum

start = time.time()
listNumbers()
print(main())
end = time.time()
print("le programme a mis ", end - start, " ms")

我怎样才能使我的程序更有效率？你知道吗

Answer 1

检查到一半，然后将所有通过的数字相加是非常低效的。
试着改变

        for k in range(1, int(i / 2) + 1):
            if i % k == 0:
                s += k

至

        for k in range(1, int(i**0.5)+1):
            if i % k == 0:
                s += k
                if k != i//k:
                    s += i//k

Answer 2

一旦你有了丰富的数字列表，你可以做一个列表result = [False] * 28123，然后

for a in abondant:
    for b in abondant:
        result[min(a+b, 28123)] = True

那么

l = []
for i in range(len(result)):
    if not result[i]:
        l.append(i)
print(l)

Answer 3

问题是在check函数中对“abondant”进行了两次迭代，调用了28111次。 只计算一次所有a+b的集合，然后检查你的数字是否在里面，效率会更高。你知道吗

比如：

def get_combinations():
    return set(a+b for a in abondant for b in abondant)

然后可能是主要功能：

def main():
    combinations = get_combinations()
    non_abondant = filter(lambda nb: nb not in combinations, range(12,l))
    return sum(non_abondant)