python求取20000以内亲密数对

原题：

 如果两个自然数a和b，a的所有因子（比a小且能整除a的自然数）之和恰好等于b，并且b的所有因子之和恰好等于a，则称a和b为一对亲密数。

例如：220和284就是一对亲密数（amicable pair），因为，

220的因子有:1,2,4,5,10,11,20,22,44,55,110,加起来等于284

284的因子有:1,2,4,71,142,加起来正好等于220

编写函数factor_sum，计算并返回自然数n的所有因子之和。例如，factor_sum(220)的返回值应该是284，factor_sum(284)的返回值应该是220。（提示：使用循环，穷举所有小于n的自然数）使用函数factor_sum，找出20000以内的所有亲密数对

样例代码：

def factor_sum(number): total=0 for i in range(1,number): if number%i==0: total+=i return total def find_all(number): a=[0] for i in range(1,number): a.append(factor_sum(i)) for i in range(1,number): for j in range(i+1,number): if a[i]==j and a[j]==i: print(i,j)

IPyton中验证：

运行find_all函数大约1分钟，主要耗时在求取存储20000以内的每个数的factor_sum的信息的列表a[]，时间复杂度为O(n^2)。

若不存储每个factor_sum，那么每次条件判断就会耗时很久，时间复杂度可能为O(n^3)或O(n^4)，所以最好存储下，因为这样factor_sum只用算一次就好了。