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

이번 글에서는 주어진 숫자가 완전수(Perfect Number)인지 판별하는 방법을 C++ 코드와 함께 살펴보겠습니다.

완전수란?

완전수란 자기 자신을 제외한 모든 양의 약수의 합이 자기 자신과 같아지는 수를 말합니다. 예를 들어 28의 경우 자기 자신을 제외한 약수는 1, 2, 4, 7, 14이며, 이들의 합은 다음과 같습니다.

1 + 2 + 4 + 7 + 14 = 28

따라서 입력값이 28이라면 출력 결과는 True가 됩니다. 문제에서 주어진 수 n의 범위는 10⁸ 이하입니다.

해결 접근 방식

완전수는 놀랍도록 드문 수입니다. 10⁸ 범위 안에 존재하는 완전수는 다음 다섯 개뿐입니다.

6
28
496
8128
33550336

따라서 매번 약수를 일일이 구해 합산하는 대신, 이 다섯 개의 값을 미리 집합(set)에 저장해 두고 입력값이 해당 집합에 포함되어 있는지만 확인하면 됩니다. 이 방식은 O(1)에 가까운 시간 복잡도로 매우 효율적입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool checkPerfectNumber(int num) {
        set<int> set={6,28,496,8128,33550336};
        return set.find(num)!=set.end();
    }
};
main(){
    Solution ob;
    cout << (ob.checkPerfectNumber(28));
}

입력

출력

코드 설명

Solution 클래스의 checkPerfectNumber 함수는 미리 정의된 완전수 집합에서 find 함수를 사용해 입력값 num이 존재하는지 검사합니다. 값이 발견되면 반복자가 end()가 아니므로 true를 반환하고, 그렇지 않으면 false를 반환합니다. main 함수에서 28을 인자로 호출했기 때문에 출력으로 1(true)이 나타납니다.

마무리

입력 범위가 제한적일 때는 수학적 성질을 활용해 가능한 값을 미리 계산해 두는 것이 가장 빠르고 간단한 해법이 될 수 있습니다. 만약 범위가 훨씬 커진다면, √n까지의 약수만 확인하는 방식으로 완전수 여부를 직접 계산하는 알고리즘을 고려해야 합니다.