python-2.7 - 在 python 中找到友好数字的最有效方法是什么？

Question

我用 Python 编写了代码来计算小于 10000 的友好数字的总和:

def amicable(a, b):
   total = 0
   result = 0
   for i in range(1, a):
      if a % i == 0:
        total += i
   for j in range(1, b):
      if b % j == 0:
        result += j
   if total == b and result == a:
        return True
   return False

sum_of_amicables = 0
for m in range (1, 10001):
    for n in range (1, 10001):
        if amicable(m, n) == True and m != n:
            sum_of_amicables = sum_of_amicables + m + n

代码在 Python 2.7.11 中运行超过 20 分钟。可以吗？我该如何改进它？

Answer 1

优化到 O(n)

def sum_factors(n):  
     result = []
     for i in xrange(1, int(n**0.5) + 1):
         if n % i == 0:
             result.extend([i, n//i])
     return sum(set(result)-set([n]))

def amicable_pair(number):
    result = []
    for x in xrange(1,number+1):
        y = sum_factors(x)
        if sum_factors(y) == x and x != y:
            result.append(tuple(sorted((x,y))))
    return set(result)

运行它

start = time.time()
print (amicable_pair(10000))
print time.time()-start

结果

set([(2620, 2924), (220, 284), (6232, 6368), (1184, 1210), (5020, 5564)])
0.180204153061

在 macbook pro 上只需 0.2 秒