골드바흐의 추측 (feat. 백준, 9020번)

골드바흐의 추측
https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/9020
#include <iostream>
#include <cmath>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register bool arr[10001] = { false };
	arr[0] = arr[1] = true;
	register int e = sqrt(10000);
	for (register int i = 2, j; i <= e; ++i)
		if (!arr[i])
			for (j = i << 1; j <= 10000; j += i)
				arr[j] = true;
	register int T, N;
	cin >> T;
	for (register int t = 0; t < T; ++t) {
		cin >> N;
		for (register int i = 0, j; i < N / 2; ++i)
			if (!arr[N / 2 - i] && !arr[N / 2 + i]) {
				cout << N / 2 - i << " " << N / 2 + i << "\n";
				break;
			}
	}
	return 0;
}
// *&)*@*

1. 주어진 값을 기준으로 절반을 나눴을때, 좌측과 우측이 소수인 경우가 가장 차이가 적은 소수입니다.
2. 좌측은 -1씩, 우측은 +1씩 옮겨가며 두 값이 모두 소수인지 확인합니다.