이번 글에서는 숫자 N이 주어졌을 때, 이를 가능한 한 많은 소수의 합으로 분해하는 문제를 다뤄보겠습니다. 먼저 예제를 통해 문제를 이해해 보겠습니다.
입력: N = 7 출력: 2 2 3 설명: 7은 2 두 개와 3 하나의 합으로 표현할 수 있으며, 이것이 가능한 최대 개수의 소수입니다. 입력: N = 17 출력: 2 2 2 2 2 2 2 3
해결 접근 방법
일반적으로 숫자를 소수의 합으로 표현하려면 N에서 소수를 하나 빼고, 남은 값이 소수인지 확인하는 방식을 떠올릴 수 있습니다. 남은 값이 소수라면 N을 두 소수의 합으로 표현할 수 있습니다.
하지만 이 문제는 소수의 개수를 최대화해야 합니다. 따라서 가장 작은 소수인 2와 3만을 사용하는 것이 유리합니다. 흥미롭게도 어떤 수든 2와 3의 조합으로 만들 수 있습니다.
N이 짝수라면, (N / 2)개의 2의 합으로 표현할 수 있습니다.
N이 홀수라면, 3 하나와 ((N − 3) / 2)개의 2의 합으로 표현할 수 있습니다.
이런 방식으로 N을 최대 개수의 소수의 합으로 표현할 수 있습니다.
참고로, 2보다 큰 모든 짝수는 두 소수의 합으로 표현될 수 있다는 골드바흐 추측(Goldbach's Conjecture)에 근거하여, 이러한 분해는 항상 가능하다고 볼 수 있습니다.
엣지 케이스 처리
N = 1: 소수의 합으로 표현할 수 없습니다.
N = 2 또는 N = 3: 자기 자신이 곧 답입니다.
C++ 구현 예제
#include <iostream>
using namespace std;
int main() {
int N = 7;
bool first = true;
// N이 홀수라면 3을 하나 출력하고 N에서 3을 뺀다
if (N % 2 == 1) {
cout << "3";
N -= 3;
first = false;
}
// 남은 N이 0이 될 때까지 2를 계속 출력한다
while (N > 0) {
cout << (first ? "" : " + ") << "2";
first = false;
N -= 2;
}
return 0;
}
출력 결과
3 + 2 + 2
복잡도 분석
시간 복잡도: O(N) — N을 2씩 줄여가며 반복하기 때문입니다.
공간 복잡도: O(1) — 추가적인 메모리를 사용하지 않습니다.
마무리
이번 튜토리얼에서는 숫자를 최대 개수의 소수의 합으로 표현하는 방법을 알아보았습니다. 가장 작은 소수인 2와 3만을 활용하는 간단한 그리디(greedy) 접근 방식으로 문제를 효율적으로 해결할 수 있습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분에게 도움이 되었기를 바랍니다.