欧拉计划 #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

一旦你有了丰富的数字列表，你就可以制作一个列表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 2

检查到一半并总结所有通过的数字是非常低效的。
尝试改变

        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 3

问题是您在调用 28111 次的检查函数中对 "abondant" 进行了两次迭代。只计算一次所有 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)

欧拉计划 #23 效率

Project Euler #23 efficiency

python

python-3.x

performance

processing-efficiency