ProjectEuler21.py

# -*- coding: utf-8 -*-
"""
Problem 21

d(n)&#12434;n&#12398;&#30495;&#12398;&#32004;&#25968;&#12398;&#21644;&#12392;&#23450;&#32681;&#12377;&#12427;&#12290;&#65288;&#30495;&#12398;&#32004;&#25968;&#12392;&#12399;n&#20197;&#22806;&#12398;&#32004;&#25968;&#12398;&#12371;&#12392;&#12391;&#12354;&#12427;&#12290;&#65289;
&#12418;&#12375;&#12289;d(a)=b &#12363;&#12388; d(b)=a &#65288;a&ne;b&#65289;&#12434;&#28288;&#12383;&#12377;&#12392;&#12365;&#12289;a&#12392;b&#12399;&#21451;&#24859;&#25968;&#65288;&#35242;&#21644;&#25968;&#65289;&#12391;&#12354;&#12427;&#12392;&#12356;&#12358;&#12290;

&#20363;&#12360;&#12400;&#12289;220&#12398;&#32004;&#25968;&#12399;1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110&#12394;&#12398;&#12391;d(220)=284&#12391;&#12354;&#12427;&#12290;
&#12414;&#12383;&#12289;284&#12398;&#32004;&#25968;&#12399;1, 2, 4, 71, 142&#12394;&#12398;&#12391;d(284)=220&#12391;&#12354;&#12427;&#12290;

&#12381;&#12428;&#12391;&#12399;10000&#26410;&#28288;&#12398;&#21451;&#24859;&#25968;&#12398;&#21512;&#35336;&#12434;&#27714;&#12417;&#12424;&#12290;
"""
import time
from math import sqrt
time1 = time.time()

SUM = 0
for i in range(5, 10000):
    sum_a = 0
    sum_b = 0
    for j in range(2, int(sqrt(i))):
        if i % j == 0:
            sum_a += j + i / j
    if int(sqrt(i)) ** 2 == i:
        sum_a += int(sqrt(i))
    sum_a += 1

    if sum_a <= i:
        continue

    for k in range(2, int(sqrt(sum_a))):
        if sum_a % k == 0:
            sum_b += k + sum_a / k
    if int(sqrt(sum_a)) ** 2 == sum_a:
        sum_b += int(sqrt(sum_a))
    sum_b += 1

    if sum_a > 10000 or sum_b > 10000:
        continue

    if sum_b == i:
        SUM += sum_a + i

print(SUM)
print(time.time() - time1, "seconds")