Python解决projecteuler问题的速度似乎很慢

Question

所以，我想解决Problem 21 from Project Euler。我想我把所有的东西都写对了，但是我不能得到最后的答案。我的意思是程序没有完全执行。你知道吗

def d(num):
    SUM = 0
    for i in range(1,num):
        if num % i == 0:
            SUM += i
    return SUM


SUM = 0
for a in range(1,10000):
    for b in range(1,10000):
        if a != b:
            if d(a) == b and d(b) == a:
                SUM += a+b

print(SUM)

Answer 1

for b in range(1, 10000)循环是不必要的，因为您知道最多有一个合适的b，如果它存在，它就等于d(a)。你知道吗

另外，要注意在最后的a和b数两次。你知道吗

SUM = 0
for a in range(1,10000):
    b = d(a)
    if a != b and d(b) == a:
        SUM += a+b

print(SUM//2)

Answer 2

这里的计算似乎太多了。第二个嵌套循环执行10000*10000次，每个循环计算d两次，结果在内部循环中平均执行10000步。这是10^12步。我相信这将是缓慢的，即使在相当强大的机器。您能想出一种方法来降低解决方案的时间复杂性吗？你知道吗

Answer 3

这不是python的问题。无论用哪种语言编写，您的算法都会运行缓慢，因为您有三个嵌套for循环，而您只能将其减少到两个。问题是，对于从1到10000的x的每个值，计算d(x)100000000次。对于每个x，应该只计算一次。你知道吗