4 이상의 모든 짝수는 두 개의 소수(Prime Number)의 합으로 표현할 수 있다는 것이 잘 알려져 있습니다. 이는 수학에서 유명한 골드바흐 추측(Goldbach's Conjecture)과 관련된 내용으로, 하나의 짝수가 여러 가지 소수 조합을 가질 수도 있다는 점이 흥미롭습니다.
예를 들어 10은 다음과 같이 두 가지 방법으로 표현할 수 있습니다.
- 10 = 5 + 5
- 10 = 7 + 3
이 글에서 소개하는 알고리즘은 주어진 짝수에 대해 가능한 모든 소수 합의 조합을 찾아 출력합니다. 핵심 아이디어는 간단합니다. 어떤 수 x가 소수일 때, (number − x) 역시 소수인지만 확인하면 됩니다. 두 값이 모두 소수라면 그 합은 곧 해당 짝수가 됩니다.
입력과 출력
입력:
짝수: 70
출력:
소수 합
70 = 3 + 67
70 = 11 + 59
70 = 17 + 53
70 = 23 + 47
70 = 29 + 41
알고리즘
dispPrimeSum(num)
입력 − 짝수.
출력 − 소수들의 합 형태로 해당 수를 화면에 표시합니다.
시작
만약 num이 홀수라면
프로그램 종료
i := 3부터 num/2까지 반복
만약 i가 소수라면
만약 (num - i)도 소수라면
"num = i + (num - i)" 형태로 출력
반복 끝
끝
C++ 구현 예제
#include<iostream>
using namespace std;
int isPrime(int number) { // 숫자가 소수인지 판별하는 함수
int lim;
lim = number / 2;
for(int i = 2; i <= lim; i++) {
if(number % i == 0)
return 0; // 약수가 존재하므로 소수가 아님
}
return 1; // 약수가 없으므로 소수임
}
void displayPrimeSum(int num) {
if(num % 2 != 0) { // 입력값이 홀수인 경우
cout << "Invalid Number";
exit(1);
}
for(int i = 3; i <= num / 2; i++) {
if(isPrime(i)) { // i가 소수라면
if(isPrime(num - i)) { // (num - i)도 소수인지 확인
cout << num << "= " << i << " + " << (num - i) << endl;
}
}
}
}
main() {
int num;
cout << "Enter an even number: "; cin >> num;
displayPrimeSum(num);
}
실행 결과
Enter an even number: 70
70 = 3 + 67
70 = 11 + 59
70 = 17 + 53
70 = 23 + 47
70 = 29 + 41
동작 원리 정리
- 입력값이 홀수이면 유효하지 않은 입력으로 처리하고 프로그램을 종료합니다.
- 3부터 num/2까지의 수를 차례대로 검사하며, 중복되는 조합(예: 3+67과 67+3)이 출력되지 않도록 절반까지만 탐색합니다.
- 현재 검사 중인 수 i가 소수이고, 동시에 (num − i)도 소수라면 두 수의 합이 원래 짝수가 되므로 결과를 출력합니다.
이처럼 단순한 완전 탐색 방식만으로도 골드바흐 추측에 따른 소수 합 조합을 손쉽게 찾을 수 있으며, 소수 판별 함수를 에라토스테네스의 체 등 더 효율적인 방식으로 개선하면 큰 수에 대해서도 빠르게 처리할 수 있습니다.