Python 似乎在解决欧拉项目问题 #21 时进展缓慢

Question

我正在尝试解决欧拉项目中的问题 21。我认为我已经正确地写了一切。但是，我无法得到最终答案，因为程序没有完全执行。

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)。

另外，请注意在最后SUM中计算每个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

从除数的角度而不是从被除数的角度来思考问题。一个关键的见解是，如果n < 10000和d是n的适当除数，那么n必须看起来像n = i*j，其中i < 100和d是i或j之一。因此，您应该能够通过嵌套循环确定范围内d[n]的所有值，其中外部循环仅执行 100 次。这个想法是创建一个所有候选n字典(值初始化为 0)，遍历所有候选i，然后将i(如果适用，j)添加到值d[n]中。以下方法有效(并解决了 100000 以外的数字的问题)：

import math
def divisor_sums(k):
s = math.ceil(math.sqrt(k))
d = {n:1 for n in range(2,k)}
d[1] = 0 #special case
for i in range(2,s):
for j in range(2,k//i):
n = i*j
d[n] += i
if s <= j: d[n] += j
return d
def amicables(k):
d = divisor_sums(k)
pairs = []
for a in range(2,k):
b = d[a]
if a != b and b < k and a == d[b] : pairs.append((a,b))
return pairs
def amicable_sum(k):
pairs = amicables(k)
return sum(a+b for a,b in pairs if a < b)

例如：

>>> amicable_sum(10000)
31626
>>> amicable_sum(100000)
852810
>>> amicable_sum(1000000)
25275024

第一个是即时的，第二个花了不到一秒钟，第三个大约 5 秒(在我的机器上)。

Answer 3

这不是 python 的问题。无论用什么语言编写，您的算法都会运行缓慢，因为您有三个嵌套的 for 循环，而您可以将其减少到只有两个。问题是您要为 1 到 10000 范围内的每个x值计算d(x)10000000 次。对于每个x，您只应计算一次。

Answer 4

这里似乎有太多的计算。你有第二个嵌套循环，执行 10000*10000，每个循环计算 d 两次，导致内部循环中平均有 10000 步。这是 10^12 个步骤。我相信即使在非常强大的机器上，这也会很慢。您能想到一种方法来降低解决方案的时间复杂度吗？