[백준] 9020_골드바흐의 추측

[문제]: 9020번: 골드바흐의 추측 (acmicpc.net)

 

체로 소수를 걸러내는건 간단하다. 

핵심은 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우 두 소수의 차이가 가장 작아야만 한다.

그렇게 하기 위해 주어진 입력 n의 중간부터 하나씩 작게 세어서 두 소수를 찾는다.

#include <iostream>
using namespace std;

bool che[10001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	fill(che, che + 10001, true);
	che[0] = che[1] = false;
	for (int i = 2; i * i <= 10000; ++i) 
		if (che[i])
			for (int j = i * i; j <= 10000; j += i)
				che[j] = false;
	
	int T; 
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
        // 여기가 핵심이다!
		for (int i = n / 2; i >= 2; --i) {
			if (che[i] && che[n - i]) {
				cout << i << ' ' << n - i << '\n';
				break;
			}
		}
	}
	return 0;
}