C++로 홀수를 소수의 합으로 표현하는 방법

문제 개요

이 문제에서는 홀수 N이 주어졌을 때, 이를 소수(prime number)들의 합으로 표현하는 것이 목표입니다. 이때 사용할 수 있는 소수는 최대 세 개입니다.

문제 이해를 위한 예시

입력: N = 55

출력: 53 + 2

풀이 접근 방법

홀수는 소수들의 합으로 나타낼 수 있으며, 다음과 같이 세 가지 경우로 나누어 생각할 수 있습니다.

• 경우 1: n 자체가 소수인 경우 → 하나의 소수 n으로 그대로 표현합니다.
• 경우 2: (n − 2)가 소수인 경우 → 두 소수 2와 (n − 2)의 합으로 표현합니다.
• 경우 3: 위 두 경우에 해당하지 않으면 → 3을 먼저 빼면 (n − 3)은 짝수가 됩니다. 골드바흐 추측에 따라 이 짝수는 두 소수의 합으로 표현할 수 있으므로, 어떤 수 A가 소수이고 {(n − 3) − A} 역시 소수인지 차례로 검사한 뒤 조건을 만족하는 조합을 출력합니다.

여기서 활용되는 골드바흐 추측(Goldbach's conjecture)은 "4보다 큰 모든 짝수는 두 소수의 합으로 표현할 수 있다"는 내용의 유명한 추측입니다. 아직 수학적으로 완전히 증명되지는 않았지만 매우 큰 범위까지 검증되어 있어, 알고리즘 문제에서는 사실상 참으로 간주하고 활용합니다.

솔루션 구현 코드

#include <iostream>
using namespace std;

bool isPrime(int x)
{
    if (x == 0 || x == 1)
        return false;
    for (int i = 2; i * i <= x; ++i)
        if (x % i == 0)
            return false;
    return true;
}

void primeAsSumofPrime(int n) {

    if (isPrime(n))
        cout<<n;
    else if (isPrime(n - 2))
        cout<<"2 "<<"+ "<<(n - 2);
    else{
        cout<<"3 "<<"+ ";
        n -= 3;
        for (int i = 0; i < n; i++) {
            if (isPrime(i) && isPrime(n - i)) {
                cout<<i<<" + "<<(n - i);
                break;
            }
        }
    }
}

int main() {

    int n = 561;
    cout<<"The number "<<n<<" expressed as sum of primes is ";
    primeAsSumofPrime(n);
    return 0;
}

실행 결과

The number 561 expressed as sum of primes is 3 + 11 + 547

위 코드에서 561은 소수가 아니고, (561 − 2) = 559 역시 소수가 아니므로 경우 3이 적용됩니다. 3을 제외한 558을 두 소수의 합으로 분해하면 11 + 547이 되고, 따라서 561은 3 + 11 + 547로 표현됩니다.

시간 복잡도

소수 판별 함수 isPrime(x)는 2부터 √x까지만 검사하므로 O(√x)의 시간이 소요됩니다. 경우 3에서는 최악의 경우 n번 반복하면서 매 단계마다 소수 판별을 수행하므로, 전체 알고리즘의 시간 복잡도는 O(n·√n)입니다.