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

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

9020번: 골드바흐의 추측

두 소수의 차가 가장 작은 것을 골라서 출력해야돼서 까다로웠던 문제였다.

 

while문 전까지는 에라토스테네스의 체를 이용하여 전체 범위의 수 중 소수를 구했다.

두 소수의 차가 가장 작은 것을 구하기 위해 함수도 만들어보고 이것저것 해봤지만 안됐고 어떤 블로그의 천재님이 해놓으신 방법을 참고하여 풀었다. 소수의 차가 가장 작으려면 최대한 중앙값을 구해야한다. 

#include <iostream>
using namespace std;

int arr[10002];

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

	int t, n;
	cin >> t;
	
	for (int i = 2; i <= 10001; i++) {
		arr[i] = 1;
	}
	for (int i = 2; i <= 10001; i++) {
		if (arr[i] == 0)
			continue;
		for (int j = i + i; j <= 10001; j += i) {
			arr[j] = 0;
		}
	}
	
	while (t--) {
		cin >> n;

		for (int i = n / 2; i > 0; i--) {
			if (arr[i] == 1 && arr[n - i] == 1) {
				cout << i << " " << n - i << '\n';
				break;
			}
		}
	}
	return 0;
}

에라토스테네스의 체는 이제 알겠는데 새로운 문제들이 참 많다..공부할게 산더미 웩