python求取20000以内亲密数对
发布时间
阅读量：
阅读量
原题：
当两个自然数a与b满足以下条件时被称为亲密数对：其中每个因子都是严格小于a且能够整除它的自然数；它们的总和正好是b；同时这些因数的总和也刚好等于另一个数字a。
例如：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中验证：
该函数运行所需时间约为1分钟。主要耗时用于获取所有小于等于20,000的整数及其factor_sum值的列表a[]。其时间复杂度为O(n²)。
如果不预先保存每个factor_sum变量，在进行条件判断时会显著增加计算时间（可能会导致的时间复杂度达到O(n³)或更高）。因此，在优化过程中建议预先保存该变量以避免重复计算。
全部评论 (0)
还没有任何评论哟~