프로젝트 오일러 021

문제

21번 문제

10000 이하 모든 친화수(우애수)의 합은?

사이냅소프트

접근

범위가 정해져있습니다. 10,000 이하의 범위에서는 N의 제곱근 이하 범위에서 나눠지는 약수를 직접 찾는 편이 빠릅니다. 약수의 합은 약수의 개수 세는 것과 아주 유사합니다. 여기서는 '자신을 제외한 약수의 합' 즉, 진약수의 합을 구하려하니 약간의 조정은 필요하겠네요.

참고로 28과 같이 진약수의 합이 자기 자신이 되는 수가 있습니다. 이러한 수를 '완전수'라고 합니다. 완전수는 약수의 합이 자기 자신이기 때문에 친화수를 이루지 못합니다. 문제를 맞게 푼 것 같은데 정답이 아닐 경우에는 완전수를 친화수에 포함하여 계산한 것이 아닌지 점검해보시기 바랍니다.

def p(n):
    s, i, l = 1, 2, int(n**0.5)
    while i <= l:
        if n % i == 0:
            s += (i + n // i)
        i += 1
    if l * l == 0:
        s -= l
    return s


def main():
    res = set()
    for x in range(10000):
        if x in res:
            continue
        y = p(x)
        if y <= 10_000 and y not in res:
            if p(y) == x and x != y:
                res.add(x)
                res.add(y)
    print(sum(res))


if __name__ == '__main__':
    main()