amicable-pair.py

class Solution:
 """
 @param: k: An integer
 @return: all amicable pairs
 """
 def amicablePair(self, k):
 # write your code here
 ret = []
 for i in range(2, k + 1):
 s = self.vsum(i)
 if (s <= i) or (s > (k + 1)):
 continue
 if i == self.vsum(s):
 ret.append([i, s])
 return ret

 def vsum(self, v):
 ret = 1
 i = 2
 while i * i < v:
 if v % i == 0:
 ret += (i + int(v / i))
 i += 1
 if i * i == v:
 ret += i
 return ret

# easy: https://www.lintcode.com/problem/243