Euler23项目：为什么我的代码这么慢，我能做些什么来加速它？

Question

下面是问题的链接：link。我的代码似乎在以指数级的速度减慢，但我无法找出原因或更有效的算法。我的方法是通过从原始数字中减去每个数字，看差值是否在富余数字列表中，来确定所有达到极限的富余数字，并确定达到上限的数字不是这些数字的和。有没有什么想法，是怎么回事，还是更好的办法来解决这个问题？你知道吗

以下是我使用的代码：

import numpy as np 
import math
import itertools

def divisors(n): return sorted(np.unique(np.array([[x,n/x] for x in range(1,int(round(math.sqrt(n))+1)) if n%x == 0]).flatten()).tolist())[0:-1]



ubound = 28123
abundant_numbers = [x for x in range(1,ubound) if x < sum(divisors(x))] 


def is_sum_of_abundant(n):
    isob = False
    for i in abundant_numbers:
        if (n - i) <=0: 
            continue
        else:
            if (n - i) in abundant_numbers:
                isob = True 
    return isob

s = 0

for x in range(1,ubound):
    print "%.2f percent\n" % ((float(x)/ubound)*100)
    if is_sum_of_abundant(x):
        print "{} is abundant".format(x)
    else:
        s+=x
        print "{} is not abundant".format(x)
print s

Answer 1

您尝试的一件事是计算除数和的更好方法—请参阅sigma函数here的定义。从本质上说，你找到了主要因素，并利用

sigma(ab) = sigma(a) * sigma(b)
sigma(p^n) = (p^(n+1)-1)/(p-1)

其中sigma（n）是正因子之和。你知道吗