골드바흐의 추측

골드바흐의 추측은 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 거임
백준 9020번 : 4<=n<=10000인 n에 대해 골드바흐 파티션 출력하기
파티션이 여러개인 경우는 두 소수의 차가 적은 것을 출력하기

풀이방법 :

• 에레토스테네스의 채를 이용해서 10000 까지의 소수를 구한다
• n이 짝수니까 n/2해서 중간값 기준으로 n/2-diff + n/2+diff = n이다. 즉 n/2-diff와 n/2+diff가 모두 소수인 diff를 찾으면 된다.

#include <iostream>
#include <cmath>

using namespace std;

//골드바흐 파티션 : 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다 
//2보다 큰 짝수 n에 대하여 n의 골드바흐 파티션 출력(두 소수의 차이가 가장 작은 경우로)

int main() {
	
	

	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int testCase = 0;
	int n = 0;

	//testCase 개수 입력 
	cin >> testCase;

	//어차피 n의 최대값이 10000이므로 10000까지의 소수를 에라토스테네스의 채로 전부 구해도 상관없다
	int prime[10001];

	//배열 초기화
	for (int i=2;i<=10000;i++){
		prime[i] = i;
	}

	for (int i = 2; i <= sqrt(10000); i++) {
		if (prime[i] == 0) {
			continue;
		}
		for (int j = i * i; j <= 10000; j += i) {
			prime[j] = 0;
		}
	}
	//~10000까지 소수인 애들 파악 
	


	int half = 0;

	int dif = 0;


	for (int i = 1; i <= testCase; i++) {

		cin >> n;

		half = n / 2;
		
		int num1 = 0, num2 = 0;
		

		dif = 0;

		while (true) {

			
			num1 = prime[half - dif];
			num2 = prime[half + dif];

			
			if (num1 == 0||num2==0) {
				dif += 1;
				continue;
			}
			else {
				cout << num1 << " " << num2 << "\n";
				break;
			}
			
		}
	



	}



	


	
	
	return 0;
}