亲和数

记d(n)为n的所有真约数（严格小于n的约数）之和。

若$d(a)=b$，$d(b)=a$，且$a\neq b$，就称$a,b$为一个亲和数对，此时$a,b$都被称为亲和数。

例如 $d(220)=1+2+4+5+10+11+20+22+44+55+100=284$，而 $d(284)=1+2+4+71+142=220$。

求所有小于10000的亲和数之和。

本题难度:

解答

先用筛法求出并保存每个数的真约数之和，再挑出对其中的亲和数对求和即可。结果是$31626$。

dSum=[1 for i in range(10000)]

for d in range(2,10000):
  for i in range(d+d,10000,d):
    dSum[i]+=d

print sum(i for i in range(2,10000) if dSum[i]<10000 and dSum[i]!=i and dSum[dSum[i]]==i)