문제 정의
주어진 양의 정수 N이 두 소수(prime number)의 합으로 표현될 수 있는지 판별하는 프로그램을 작성해야 합니다.
접근 방법
먼저 간단한 예시를 통해 문제를 이해해 보겠습니다.
예를 들어 20은 다음과 같이 두 소수의 합으로 나타낼 수 있습니다.
- 20 = 3 + 17
- 20 = 13 + 7
반면 11처럼 두 소수의 합으로 표현할 수 없는 숫자도 존재합니다. 참고로 골드바흐 추측에 따르면 2보다 큰 모든 짝수는 두 소수의 합으로 표현될 수 있다고 알려져 있으며, 이 프로그램은 그러한 성질을 직접 코드로 확인해 볼 수 있는 좋은 예제입니다.
알고리즘
주어진 숫자를 두 소수의 합으로 표현할 수 있는지 확인하는 절차는 다음과 같습니다.
- 입력 단계: 검사할 숫자를 실행 시점에 입력받습니다.
- 반복 단계: i를 2부터 num/2까지 증가시키며 반복합니다.
- 소수 검사 1: i가 소수인지 확인합니다.
- 소수 검사 2: i가 소수라면 (num − i) 역시 소수인지 확인합니다.
- 결론 도출: i와 (num − i)가 모두 소수라면, 주어진 숫자는 두 소수의 합으로 표현할 수 있습니다.
C 프로그램 예제
다음은 위 알고리즘을 그대로 구현한 전체 C 프로그램입니다.
#include <stdio.h>
int sum(int n);
int main(){
int num, i;
printf("Enter number: ");
scanf("%d", &num);
int flag = 0;
for(i = 2; i <= num/2; ++i){
if (sum(i) == 1){
if (sum(num-i) == 1){
printf("\nThe given %d can be expressed as the sum of %d and %d\n\n", num, i, num - i);
flag = 1;
}
}
}
if (flag == 0)
printf("The given %d cannot be expressed as the sum of two prime numbers\n", num);
return 0;
}
// 숫자가 소수인지 확인하는 함수
int sum(int n){
int i, isPrime = 1;
for(i = 2; i <= n/2; ++i){
if(n % i == 0){
isPrime = 0;
break;
}
}
return isPrime;
}
코드 설명
sum()함수는 인자로 받은 숫자가 소수이면 1을, 아니면 0을 반환합니다.main()함수에서는 2부터 num/2까지의 모든 i에 대해 i와 (num − i)가 동시에 소수인지 검사합니다.- 조건을 만족하는 조합이 발견되면 화면에 출력하고, flag 변수로 표현 가능 여부를 기록합니다.
- 모든 반복이 끝난 후에도 flag가 0이라면, 해당 숫자는 두 소수의 합으로 표현할 수 없는 것입니다.
실행 결과
위 프로그램을 컴파일하여 실행하면 다음과 같은 출력을 확인할 수 있습니다.
Run 1: Enter number: 34 The given 34 can be expressed as the sum of 3 and 31 The given 34 can be expressed as the sum of 5 and 29 The given 34 can be expressed as the sum of 11 and 23 The given 34 can be expressed as the sum of 17 and 17 Run 2: Enter number: 11 The given 11 cannot be expressed as the sum of two prime numbers
마무리
이 프로그램은 가능한 모든 조합을 하나씩 검사하는 브루트포스 방식이므로 시간 복잡도는 대략 O(N²)입니다. 다루는 숫자가 커질 경우에는 에라토스테네스의 체를 활용해 미리 소수 목록을 만들어 두면 탐색 속도를 크게 개선할 수 있습니다.