C++에서 합이 주어진 N과 같은 최대 소수 개수 구하기

문제 개요

이 문제에서는 하나의 숫자 N이 주어지며, 그 합이 정확히 N이 되도록 하는 소수의 최대 개수를 구하는 것이 목표입니다.

소수(素數)란 1과 자기 자신으로만 나누어 떨어지는 수를 의미합니다. 즉, 2, 3, 5, 7, 11처럼 1보다 크면서 약수가 자기 자신과 1뿐인 수입니다.

예시로 이해하기

입력 − N = 9

출력 − 4

설명 −

9는 다음과 같은 방법으로 소수의 합으로 표현할 수 있습니다:
2, 2, 2, 3
3, 3, 3
2, 2, 5
2, 7
이 중 가장 많은 소수를 사용한 경우는 4개입니다.

접근 방법

사용되는 소수의 개수를 최대화하려면, 합을 만들 때 가능한 한 작은 소수를 반복해서 더해야 합니다. 가장 작은 소수는 2이고, 그다음으로 작은 소수는 홀수인 3입니다. 따라서 오직 2와 3만 사용하여 합을 계산하면 소수의 개수가 최대가 됩니다.

이 아이디어를 바탕으로 문제를 두 가지 경우로 나눌 수 있습니다.

경우 1 − N이 짝수인 경우: 합을 이루는 모든 소수를 2로만 구성할 수 있습니다. 따라서 개수는 n/2가 됩니다.

경우 2 − N이 홀수인 경우: 하나의 소수만 3을 사용하고 나머지는 모두 2로 구성합니다. 따라서 개수는 (n−1)/2가 됩니다.

흥미롭게도 두 경우 모두 정수 나눗셈 n / 2 하나로 처리할 수 있습니다. C++에서 홀수에 대한 정수 나눗셈은 자동으로 소수점 이하를 버리므로, 홀수일 때 n/2의 결과가 곧 (n−1)/2와 같아지기 때문입니다.

C++ 구현 예제

다음은 합이 주어진 N과 같은 최대 소수 개수를 구하는 C++ 프로그램입니다.

#include <iostream>
using namespace std;
int maxPrimeCount(int n){
    // 홀수인 경우에도 결과는 (n-1)/2와 동일함
    return n / 2;
}
int main(){
    int n = 9;
    cout<<"합이 "<<n<<"과 같은 최대 소수 개수는 "<<maxPrimeCount(n)<<"개입니다";
    return 0;
}

실행 결과

합이 9과 같은 최대 소수 개수는 4개입니다

정리

이 문제의 핵심은 가장 작은 소수인 2를 최대한 활용한다는 발상입니다. N이 짝수이면 전부 2로, 홀수이면 3 하나와 나머지 2로 표현하면 되며, 이를 통해 복잡한 탐색 없이 O(1) 시간 복잡도로 답을 구할 수 있습니다.