파이썬으로 닫힌 구간 [2, n]에서 모든 완전수를 찾아 출력하는 방법

완전수란 무엇일까요?

완전수(perfect number)는 자기 자신을 제외한 양의 약수, 즉 진약수(proper divisor)의 합이 자기 자신과 같아지는 양의 정수입니다. 가장 작은 완전수는 6이며, 1 + 2 + 3 = 6처럼 진약수의 합이 정확히 일치합니다.

그다음 완전수는 28로, 1 + 2 + 4 + 7 + 14 = 28을 만족합니다. 이후에는 496, 8128처럼 훨씬 큰 완전수가 아주 드물게 등장합니다.

닫힌 구간 [2, n]에서 완전수 찾기

주어진 범위 안의 각 숫자에 대해 “진약수의 합이 그 수와 같은가?”라는 조건을 하나씩 검사하면 해당 구간에 존재하는 모든 완전수를 찾을 수 있습니다. 파이썬에서는 바깥쪽 반복문으로 구간의 수를 순회하고, 안쪽 반복문으로 약수를 찾아 누적하는 방식으로 간단하게 구현할 수 있습니다.

예제 코드

def print_perfect_nums(n):
    for i in range(2, n + 1):      # 닫힌 구간 [2, n]을 순회
        total = 0
        for x in range(1, i):
            if i % x == 0:         # x가 i의 약수인지 확인
                total += x         # 약수라면 합계에 누적
        if total == i:             # 진약수의 합이 자기 자신과 같으면 완전수
            print(i)

print_perfect_nums(300)

실행 결과

6
28

코드 동작 원리

1. 구간 순회: range(2, n + 1)로 닫힌 구간 [2, n]의 모든 정수를 차례대로 확인합니다.
2. 약수 판별: i % x == 0 조건으로 x가 i의 약수인지 검사하고, 참이면 total에 더합니다.
3. 완전수 판정: 안쪽 반복문이 끝난 후 total이 i와 같으면 i를 완전수로 출력합니다.

성능 개선 팁

위 방식은 각 수마다 1부터 i-1까지 모두 검사하므로 구간이 커지면 속도가 느려집니다. 약수는 쌍으로 존재하기 때문에 √i까지만 검사하고 짝이 되는 약수를 함께 더하면 실행 시간을 크게 줄일 수 있습니다.

def print_perfect_nums_fast(n):
    for i in range(2, n + 1):
        total = 1                      # 1은 항상 약수
        for x in range(2, int(i ** 0.5) + 1):
            if i % x == 0:
                total += x
                if x != i // x:        # 제곱근 중복 방지
                    total += i // x
        if total == i:
            print(i)

print_perfect_nums_fast(10000)

이 최적화 버전을 실행하면 10000 이하에 존재하는 네 개의 완전수 6, 28, 496, 8128이 모두 출력됩니다.