在python中找到友好数字的最有效方法是什么? [英] What is the most efficient way to find amicable numbers in python?

问题描述

我用 Python 编写了代码来计算 10000 以下的友好数字之和:

I've written code in Python to calculate sum of amicable numbers below 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 分钟.可以吗?我该如何改进?

Code is running more than 20 minutes in Python 2.7.11. Is it ok? How can I improve it?

推荐答案

优化为 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 秒

takes only 0.2 seconds on macbook pro

这篇关于在python中找到友好数字的最有效方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！