골드바흐의 추측

알고리즘 구분 : 수학, 정수론, 소수 판정, 에라토스테네스의 체

문제

1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.

출력
각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

제한
4 ≤ n ≤ 10,000
예제 입력 1
3
8
10
16
예제 출력 1
3 5
5 5
5 11

문제 풀이

골드바흐 수는 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다라는 것인데, 여기서 짝수와 소수라는 두 정의에 대해 파악해보아야 한다. 모든 짝수는 짝수 + 짝수, 홀수 + 홀수로 구성되며, 짝수 + 홀수로의 구성은 불가능하다. 이러한 환경에서, 짝수이면서 소수인 수는 2밖에 존재하지 않는다. 즉, 짝수이면서 소수인 두 수의 합으로 나타낼 수 있는 골드바흐 수는 4밖에 없다는 것이다. 6 이상 10000 이하인 모든 짝수의 골드바흐 파티션은 홀수 + 홀수 구성이라는 것을 알 수 있다. 그렇기에 find method에서 해당 수를 절반으로 나눈 뒤, first는 2씩 감소하면서, second는 2씩 증가시키면서 두 수가 모두 소수인 경우를 찾는 방식으로 골드바흐 파티션을 확인할 수 있도록 소스 코드를 구현했다. 또한 소수 판별을 위해서 primeArr() method를 통해 에라토스테네스의 체를 구현하여 확인할 수 있도록 하였다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

int t, n;
pair<int, int> goldbach[5001];
bool sosu[10001];
void primeArr();
void find();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> t;
	
	primeArr();
	find();
	
	for(int i = 0; i < t; i++) {
		cin >> n;
		cout << goldbach[n / 2].first << " " << goldbach[n / 2].second << endl;
	}
	
	return 0;
}

void primeArr() {
	int m = sqrt(10000);
	
	fill_n(sosu, 10001, true);
	
	for(int i = 2; i < m + 1; i++) {
		if(sosu[i] == true) {
			for(int j = (i * 2); j < 10001; j += i) {
				sosu[j] = false;
			}
		}
	}
}

void find() {
	int first, second;
	
	goldbach[2] = {2, 2};
	goldbach[3] = {3, 3};
	
	for(int i = 8; i < 10001; i += 2) {
		if((i / 2) % 2 != 0) {
			first = (i / 2);
			second = (i / 2);
		}
		else {
			first = (i / 2) - 1;
			second = (i / 2) + 1;
		}
		
		for(; first != 1;) {
			if(sosu[first] == true && sosu[second] == true) {
				goldbach[i / 2] = {first, second};
				break;
			}
			
			first -= 2;
			second += 2;
		}
	}
}

• 문제 출처 : https://www.acmicpc.net/problem/9020
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.