백준 / 수학 / 9020번 / 골드바흐의 추측 / C++

문제

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

 

<내풀이>

#include <iostream>
using namespace std;

const int N = 10001;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	bool arr[N];
	fill_n(arr, N, true);
	arr[0] = arr[1] = false;
	
	for(int i=2; i*i<=N; i++) {
		if(arr[i]) {
			for(int j=i*2; j<=N; j+=i) {
				arr[j] = false;
			}
		}
	}
	
	int t;
	cin >> t;
	
	for(int i=0; i<t; i++) {
		int n;
		cin >> n;
		
		bool flag = false;
		for(int j=n/2; j>=2; j--) {
			if(arr[j]) {
				for(int k=j; k<n; k++) {
					if(arr[k] && (j+k == n)) {
						cout << j << " " << k << '\n';
						flag = true;
						break;
					}
				}
			}
			if(flag) break;
		}
	}
	
	return 0;
}

---

일단 소수구하는 알고리즘으로 '에라토스테네스의 체'를 사용했다.

(자세한 것은 밑의 포스팅 참조)

2022.01.16 - [ALGORITHM/개념] - 에라토스테네스의 체

에라토스테네스의 체

 

그리고나서 답을 찾아냈는지를 판단하는 bool형 변수 flag를 설정했다.

두 소수의 차가 가장 적은것을 출력해야 하기때문에, 입력받은 수의 1/2 부터 반복문을 시작했다.

 

예를들어, 두 자연수의 합으로 숫자 5를 나타낸다고 해보자.

(1,4), (2,3), (3,2), (4,1) 이 있는데,

1 2 3 4 5 에서 (2,3)이 (1,4)보다 서로의 거리가 더 가깝고, 5의 반인 2.5에 가장 근접하기 때문이다.

따라서 두 수중에 작은수는 중간부터 값을 줄여나가면서 찾으면되고, 큰수는 중간부터 값을 늘려가면서 찾으면 된다.

 

따라서 if문으로 둘다 소수이고, 두 소수의 합이 입력받은 값과 일치할경우, flag를 true로 바꿔주고 출력한뒤,

반복문을 빠져나오면 된다.

 

flag를 설정한 이유는 반복문이 계속될경우 조건을 만족하는 모든 순서쌍을 출력하기 때문이다.

처음 찾은 값이 중간에서 가장 가까운 값이므로 처음 찾자마자 flag를 바꿔주면 된다.

---

<다른 사람의 풀이>

#include <iostream>
using namespace std;

int T;
int arr[10001] = { 0, }; // 0 = prime number, 1 = composite number

//에라토스테네스의 체
void isPrimeNum() {
	for(int i = 2; i<10001; i++){
		for (int j = i*2; j < 10001; j += i) {
			arr[j] = 1;
		}
	}
}

int Answer(int num) {
	//절반부터 탐색
	int length = num / 2;
	for (int i = 0; i < length; i++) {
		int temp1 = length - i;
		int temp2 = num - temp1;

		// 배열에 접근한 뒤, 둘 다 소수이면 출력
		if (arr[temp1] == 0) {
			if (arr[temp2] == 0) {
				cout << temp1 << ' ' << temp2 << '\n';
				return 0;
			}
		}
	}
	return 1;
}

int main() {
	isPrimeNum();

	cin >> T;

	for (int i = 0; i < T; i++) {
		int num;
		cin >> num;
		Answer(num);
	}

	return 0;

}

---

풀이 자체는 내풀이와 비슷하다.

하지만 반복문의 갯수가 하나 줄었다.

 

반복문을 하나 더 쓸필요없이, 변수를 선언해 값에서 빼주면서 중간을 기준으로 반대에 있는 값에 접근할 수 있다.