[C++] 백준 6588번 - 골드바흐 추측

2학년때 정수론 배울때 잠깐 언급됬던 골드바흐 추측

 

에라토스테네스 체를 활용한 문제였다.

주어진 n의 max값이 1000000이기 때문에 접근할때 for문을 두개 돌려버리면 당연히 시간초과가 날 것 같았다.

(실제로 시간초과가 났다)

그래서 algorithm stl에 들어있는 binary_search를 활용했다.

처음에 에라토스테네스의 체를 초기화해줄때 소수의 개수를 셌는데, 78498개나 나왔다.

어차피 배열에 저장할때는 오름차순으로 정렬이 되니,

정렬되어 있는 배열에서 이진탐색으로 찾으면 빠를거라고 예상했다.

찾기만 하면 나머지 수는 입력된 수에서 빼면 된다.

 

다른분의 숏코딩을 보니 문제에서 골드바흐 추측을 벗어나는 문제는 없었다.

이럴거면 나도 중간에 조건문 쓰지 말껄이라는 후회는 들긴 한다.

그리고 에라토스테네스 체를 처음에 초기화할때 조심해야했는데,

i*i 로 j쪽을 돌렸는데 여기서 숫자가 6자리 넘어갈 때 int overflow가 발생했었다.

 

#include <bits/stdc++.h>
#define endl '\n'
#define MAX 1000000 
using namespace std;

int p[MAX]; 
int pn = 0; 
bool c[MAX + 1]; 


void eratostenes_init() {
	for (int i = 2; i <= MAX; i++) {
		if (c[i] == false) {
			p[pn++] = i;
			for (int j = i * 2; j <= MAX; j += i) {
				c[j] = true;
			}
		}
	}
}

int main() {

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

	eratostenes_init();

	int n;
	while (true) {
		cin >> n;
		bool found = false;
		if (n == 0) break;

		bool temp;
		for (int i = 1; i < pn; i++) {
			temp = binary_search(p, p + pn, n - p[i]);
			if (temp) { 
				cout << n << " = " << p[i] << " + " << n - p[i] << endl; 
				found = true;
				break;
			}
		}

		if (!found) {
			cout << "Goldbach's conjecture is wrong." << endl;
		}
	}

	return 0;
}