C++로 거의 완전수(Almost Perfect Number) 판별하기

거의 완전수(Almost Perfect Number)는 '최소 결핍수(least deficient number)' 또는 '약간 결핍수(slightly defective number)'라고도 불리며, 1과 자기 자신을 포함한 모든 약수의 합이 2n-1과 정확히 일치하는 수를 의미합니다.

일반적인 완전수(perfect number)가 약수의 합이 2n과 같은 수라면, 거의 완전수는 그 값에서 정확히 1이 작은 경우입니다. 이 글에서는 주어진 수가 거의 완전수인지 판별하는 알고리즘을 C++ 코드와 함께 살펴보겠습니다.

개념 이해를 위한 예시

입력 : 16
출력 : YES
설명 :
16의 약수는 1, 2, 4, 8, 16입니다.
약수의 합 = 1 + 2 + 4 + 8 + 16 = 31
n = 16 ; 2n-1 = 2 × 16 - 1 = 31

입력 : 12
출력 : NO
설명 :
12의 약수는 1, 2, 3, 4, 6, 12입니다.
약수의 합 = 1 + 2 + 3 + 4 + 6 + 12 = 28
n = 12 ; 2n-1 = 2 × 12 - 1 = 23

위 예시에서 볼 수 있듯이, 16의 약수 합(31)은 2×16-1과 정확히 일치하므로 거의 완전수에 해당하지만, 12의 약수 합(28)은 2×12-1인 23과 다르므로 거의 완전수가 아닙니다.

참고로, 현재까지 알려진 거의 완전수는 모두 2의 거듭제곱(1, 2, 4, 8, 16, ...)뿐이며, 이 외의 거의 완전수가 존재하는지는 아직 밝혀지지 않았습니다.

알고리즘

주어진 수가 거의 완전수인지 판별하는 절차는 다음과 같습니다.

입력받은 수 n의 모든 약수의 합(sum)을 계산합니다.
비교 기준값 val = 2n - 1을 계산합니다.
sum == val이면 "YES"를 출력합니다.
그렇지 않으면 "NO"를 출력합니다.

C++ 구현 코드

#include <iostream>
using namespace std;

// 거의 완전수 여부를 판별하는 함수
void almostPerfectNumber(int n);

int main() {
    int n = 16;
    cout<<n<<" 은(는) 거의 완전수인가요?\n";
    almostPerfectNumber(n);
}

void almostPerfectNumber(int n) {
    int divisors = 0;   // 약수의 합을 저장할 변수

    // 1부터 n까지 반복하며 약수를 찾아 합산
    for (int i = 1; i <= n; i++) {
        if (n % i == 0)
            divisors += i;
    }

    // 약수의 합이 2n - 1과 같은지 비교
    if (divisors == 2 * n - 1)
        cout<<"YES";
    else
        cout<<"NO";
}

실행 결과

16 은(는) 거의 완전수인가요?
YES

코드 동작 원리 및 성능

이 코드는 1부터 n까지 모든 수를 직접 나누어 떨어지는지 확인하는 방식으로 약수를 찾습니다. 시간 복잡도는 O(n)이며, 약수는 쌍으로 존재한다는 성질을 활용해 √n까지만 검사하면 O(√n)으로 최적화할 수 있습니다. 큰 수를 다룰 때는 후자의 방식이 훨씬 효율적입니다.