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

백준 9020 골드바흐의 추측

• https://www.acmicpc.net/problem/9020

#include <iostream>
using namespace std;

int isPrime[10000] = { 0 };
//n 소수면 isPrime[n] = 0

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

	isPrime[0] = isPrime[1] = 1;
	for (int i = 2; i <= 100; i++) 
		if (!isPrime[i]) 
			for (int j = i * i; j <= 10000; j += i) 
				isPrime[j] = 1;
		
	int t, n;
	cin >> t;

	while (t--) {
		cin >> n;

		//n/2가 소수인 경우
		if (!isPrime[n / 2]) {
			cout << n / 2 << " " << n / 2 << endl;
			continue;
		}

		//n/2보다 작은, 가장 큰 소수 prime
		int prime = (n / 2) - 1;

		while (1){ 
			if ((!isPrime[prime])&&(!isPrime[n - prime])) break;
			else prime--;
		}
		cout << prime << " " << n -prime << endl;
	}

	return 0;
}