Amicable Number
题目描述
就是 数A 的所有因数(包括1，不包括A) 之和 等于 B。B的所有因数之和又刚好为A。 且 A != B. 求[1, N] 中所有符合条件的pair.
解题方法
brute force
对于整数i, 找出所有1-n之间的i的因数和，保存在一个array里。
如果对于i,检查所有1-i是否是i的因子，那么这个时间复杂度就是O(n^2).
然后遍历这个array，找出符合条件的Pair, 时间复杂度O(n)
- time
O(n^2 + n) = O(n^2) - space
O(n)
优化，如果找因子只查到sqrt(i)，就是O(n^3/2)
O（nlogn)的方法
利用类似count prime的方法找因子, 将他们存到array里
def generate(n):
divisor_sum = [1 for i in range(n+1)]
for i in range(2, n+1):
j = i + i
while j <= n:
divisor_sum[j] += i
j += i
return dp
那么对于这一过程的时间复杂度是, 是一个Harmonic series
O(n/2 + n/3 + n/4 + .... + 1) = O(logn)
那个计算因子和的过程就是O(nlogn)
Solution
def generate(n):
divisor_sum = [1 for i in range(n+1)]
for i in range(2, n+1):
j = i + i
while j <= n:
divisor_sum[j] += i
j += i
return dp
def find_pair(n):
results = []
divisor_sum = generate(n)
for i in range(1, n+1):
j = divisor_sum[i]
if i < j and j <= n and divisor_sum[j] == i:
results.append((i, j))
return results