C++로 숫자를 두 소수의 합으로 표현할 수 있는지 확인하는 방법

이 글에서는 하나의 숫자가 두 개의 소수(prime number)의 합으로 표현될 수 있는지 확인하는 C++ 프로그램을 다룹니다. 이 문제는 유명한 '골드바흐의 추측'과 관련이 있는데, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 내용입니다.

전체 예제 코드

#include <iostream>
using namespace std;
int func(int num) {
    int i;
    int flag = 1;
    for(i = 2; i <= num/2; ++i) {
        if(num % i == 0) {
            flag = 0;
            break;
        }
    }
    return flag;
}
int main() {
    int num , i;
    cout << "Enter a number : \n";
    cin >> num;
    for(i = 2; i <= num/2; ++i) {
        if (func(i)) {
            if (func(num - i)) {
                cout << num << " = " << i << " + " << num-i << endl;
            }
        }
    }
    return 0;
}

실행 결과

Enter a number : 18
18 = 5 + 13
18 = 7 + 11

코드 동작 원리

1. 소수 판별 함수 func()

프로그램에서 핵심 역할을 하는 func() 함수는 입력받은 숫자가 소수인지 아닌지를 판별합니다.

int func(int num) {
    int i;
    int flag = 1;
    for(i = 2; i <= num/2; ++i) {
        if(num % i == 0) {
            flag = 0;
            break;
        }
    }
    return flag;
}

동작 방식은 다음과 같습니다.

• flag 변수를 1(소수라고 가정)로 초기화합니다.
• 2부터 num의 절반까지 반복하면서 num을 i로 나눈 나머지가 0인지 검사합니다.
• 나누어 떨어지는 약수가 발견되면 flag를 0으로 설정하고 반복문을 종료합니다.
• 최종적으로 flag 값(1 또는 0)을 반환하여 소수 여부를 알려줍니다.

2. main() 함수의 처리 과정

main() 함수에서는 사용자로부터 숫자를 입력받고, 해당 숫자를 두 소수의 합으로 나타낼 수 있는 모든 경우를 찾습니다.

cout << "Enter a number : \n";
cin >> num;
for(i = 2; i <= num/2; ++i) {
    if (func(i)) {
        if (func(num - i)) {
            cout << num << " = " << i << " + " << num-i << endl;
        }
    }
}

처리 흐름을 정리하면 다음과 같습니다.

• 사용자가 숫자를 입력합니다.
• i를 2부터 num/2까지 증가시키면서 각 값에 대해 func(i)를 호출해 i가 소수인지 확인합니다.
• i가 소수라면, 남은 값인 num - i도 func()를 통해 소수인지 검사합니다.
• 두 값이 모두 소수일 경우, "num = i + (num - i)" 형태로 화면에 출력합니다.

예를 들어 18을 입력하면 2부터 9까지의 수 중 소수인 값과 그 짝이 되는 소수를 찾아 18 = 5 + 13, 18 = 7 + 11 두 가지 조합을 결과로 보여줍니다.