C++로 어떤 수를 두 과잉수(Abundant Number)의 합으로 표현할 수 있는지 확인하는 방법

어떤 수가 주어졌을 때, 이 수를 두 개의 과잉수(Abundant Number)의 합으로 표현할 수 있는지 확인하는 문제입니다. 표현이 가능하다면 해당하는 두 수를 출력하고, 불가능하다면 -1을 출력해야 합니다.

과잉수란?

과잉수란 자기 자신을 제외한 약수(진약수)의 합, 즉 sum(n)이 그 수 자체의 값보다 큰 수를 말합니다. 예를 들어 12의 진약수는 1, 2, 3, 4, 6이며, 이들의 합은 16으로 12보다 크기 때문에 12는 과잉수에 해당합니다.

문제 해결 접근 방식

이 문제를 해결하기 위해 다음과 같은 전략을 사용합니다.

먼저 주어진 범위 내의 모든 과잉수를 미리 계산하여 집합(set)에 저장합니다. 이때 각 수의 약수 합은 제곱근까지만 탐색하면 되므로 효율적으로 구할 수 있습니다. 그다음 주어진 수 n에 대해 i = 1부터 n까지 반복하면서, i와 (n − i)가 모두 과잉수인지 확인합니다. 두 수가 모두 과잉수라면 그 쌍을 출력하고 함수를 종료하며, 끝까지 찾지 못했다면 -1을 출력합니다.

예제 코드

#include <iostream>
#include <set>
#define N 100005
using namespace std;
set<int> getAbundantSet() {
    set<int> abundant_set;
    for (int i = 1; i < N; i++) {
        int sum = 1;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                sum += j;
                if (i / j != j)
                sum += i / j;
            }
        }
        if (sum > i)
            abundant_set.insert(i);
    }
    return abundant_set;
}
void representSumAbundant(int number){
    set<int> abundant_set = getAbundantSet();
    for (int i = 1; i <= number; i++) {
        if (abundant_set.count(i) && abundant_set.count(number - i)) {
            cout << i << " " << number - i;
            return;
        }
    }
    cout << -1;
}
int main() {
    int n = 30;
    representSumAbundant(n);
}

실행 결과

12 18

결과 분석

n = 30이 주어진 경우, 프로그램은 12와 18을 출력합니다. 12의 진약수 합은 16, 18의 진약수 합은 21로 두 수 모두 과잉수이며, 12 + 18 = 30이 성립하기 때문입니다.

시간 복잡도

과잉수 집합을 생성하는 과정은 각 수마다 약수를 제곱근 범위에서 탐색하므로 O(N√N)의 시간이 걸리며, 두 수의 조합을 찾는 과정은 O(N)입니다. 따라서 전체 시간 복잡도는 O(N√N)이고, 집합 저장을 위한 공간 복잡도는 O(N)입니다.