[ 백준 9020] 골드바흐의 추측(C++)

9020번: 골드바흐의 추측

 

 

문제!

---

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의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

 

---

요약하면 숫자 n에 대해서 두 소수의 차이가 가장작은 합으로 표현되게 만들어 달라는 문제입니다

 

 

문제자체는 직관적인 문제여서 어떤것 부터 먼저 해야할지부터 나열해보겠습니다.

1. 일단 소수를 구해놔야 할것같습니다. 매번 구하기에는 계산이 많아질듯... 10000까지의 소수만 구해주면되겠네요

2. 어떻게 나눌것인가에 대해서 생각해봐야 할것 같네요

 

 

일단 소수는 "에라토스테네스의 체" 알고리즘을 사용하면 쉽게 구할수있습니다!

 

이 알고리즘의 방식은 1~n까지의 숫자를 나열해놓고 2의 배수, 3의 배수 ,.... 차례대로 제거해주는 방법입니다

소수를 구하기위해서 일일히 나눠지는지 파악하는 함수보다는 훨씬 빠릅니다!

 

그럼이제 소수를 구했으니 어떻게 나눌것인가....

저는 바로 n을 반토막내어 생각했습니다.

소수는 정해져있습니다. {1,2,3,5,7,...} 이중에서 차이가 가장작은 두개를 골라 n을 만들어야 하기에

가운데, n/2와 가장 가까운숫자 부터 생각해보기로 했습니다

 

차례대로 하나씩 변경해나가며 합이 n이 되는지! 판단하여 출력!

 

먼가 말이 길어졌네요 바로 시작해보겠습니다.

 

 

시작!

---

먼저 에라토스테네스의 체 알고리즘을 사용하여 소수들을 모두 구해줍시다.

vector <int>num(10001); // 소수아닌걸 1로


vector <int>num_list;


for (int i = 2; i < 10001; i++) { // 소수
		int k = i + i;
		while (k <= 10000) {
			num[k] = 1;
			k = k + i;
		}
	}

	for (int i = 1; i < 10001; i++) {
		if (num[i] == 0) {
			num_list.push_back(i);
		}
	}

 

 

다음은 입력을 받고

int n = 0;

	cin >> n;

	while(n--) {
		int memo = 0;

		cin >> memo;

 

다음은 lower_bound(이분탐색) 함수를 통해 n/2와 같거나 큰 수를 먼저 찾아줍시다.

int p1 = 0;
		int p2 = 0;

		p1 = lower_bound(num_list.begin(), num_list.end(), memo / 2) - num_list.begin();
		p2 = p1;
		
		while (num_list[p1] + num_list[p2] != memo) {
			if (num_list[p1] + num_list[p2] > memo) {
				p1 -= 1;
			}
			else {
				p2 += 1;
			}
		}

그리고 그 위치에서 p1,p2를 설정해주고 

현재합이 크면 p1을 줄여주고

현재합이 작으면 p2를 늘려주어

가운데에서 넓혀가며 탐색해줍시다!

 

 

마지막엔 잊지말고 인덱스를 값으로 변환하여 출력해줍시다.

cout << num_list[p1] << " " << num_list[p2] << '\n';

 

 

 

여기까지 하면 끝!

 

생각보다 바로바로 풀리는 문제였습니다.

 

 

ALL

#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;


vector <int>num(10001); // 소수아닌걸 1로


vector <int>num_list;


int main() {
	// 소수를 구해놓고 이분탐색마냥 n/2보다 작은값들의합?

	cin.tie(0);
	ios::sync_with_stdio(0);


	for (int i = 2; i < 10001; i++) { // 소수
		int k = i + i;
		while (k <= 10000) {
			num[k] = 1;
			k = k + i;
		}
	}

	for (int i = 1; i < 10001; i++) {
		if (num[i] == 0) {
			num_list.push_back(i);
		}
	}

	int n = 0;

	cin >> n;

	while(n--) {
		int memo = 0;

		cin >> memo;

		int p1 = 0;
		int p2 = 0;

		p1 = lower_bound(num_list.begin(), num_list.end(), memo / 2) - num_list.begin();
		p2 = p1;
		
		while (num_list[p1] + num_list[p2] != memo) {
			if (num_list[p1] + num_list[p2] > memo) {
				p1 -= 1;
			}
			else {
				p2 += 1;
			}
		}

		cout << num_list[p1] << " " << num_list[p2] << '\n';
	}

	return 0;

}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!