在 python 中找到友好数字的最有效方法是什么? [英] What is the most efficient way to find amicable numbers in python?
本文介绍了在 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屋!
查看全文