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

정답 코드를 바로 보기보다는 아래 글을 먼저 읽고 푸시길 바랍니다.

https://pushback.tistory.com/8

소수 문제 해결의 기본

---

 

 입력으로 들어오는 \(n\)의 범위가 \(1 \leq n \leq 10,000\)이라 에라토스테네스의 체가 필요없을 수도 있다고 생각할 수 있다.

 하지만 테스트 케이스의 수가 존재하고 문제에서 언급은 안되어 있지만 대략 \(T\)의 범위가 \(1 \leq T \leq 10,000\)라고 가정했을 때, 우리는 최악의 상황에서 \((10,000 * 10,000)\)번의 나누기 연산이 필요하다.

 TLE의 위험이 도사리고 있으니 안전하게 에라토스테네스의 체를 사용하자.  그냥 소수 문제에선 에라토스테네스의 체가 거의 정답이다.

 

 에라토스테네스의 체를 사용하여 \(1 ~ 10,000\) 사이에 있는 모든 소수를 구했다고 가정하자.

 어떤 입력 \(n\)이 들어왔을 때, 우리는 \(x + y = n, (x \leq y)\)을 만족하는 두 소수 \(x, y\)가 있다고 가정하면 \(x\)는 \(2 \leq x \leq \frac{n}{2}\)을 만족한다.

 결국, \(2\)부터 \(\frac{n}{2}\)까지 for문을 돌면서 \(x\)와 \(n - x\)가 둘 다 소수인 경우를 구해주면 된다.

 \(2\)부터 for문을 돌 때 두 수의 차가 가장 적은 것을 찾아야하므로, 찾을 때마다 답을 update해주면 마지막으로 나온 답은 자동적으로 두 수의 차가 가장 적은 경우가 된다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MAX_N = 1e4 + 1;
const int MOD = 1e+9;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

bool isPrime[MAX_N];

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    memset(isPrime, 1, sizeof(isPrime));

    isPrime[1] = false;
    for (int i = 2; i < MAX_N; ++i) {
        if (isPrime[i]) {
            for (ll j = i * 1LL * i; j < (ll) MAX_N; j += i * 1LL) {
                isPrime[j] = false;
            }
        }
    }

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int left = 2, right;

        for (int x = 2; x <= (n / 2); x++) {
            if (isPrime[x] && isPrime[n - x]) {
                left = x;
                right = n - x;
            }
        }
        cout << left << ' ' << right << '\n';
    }

    return 0;
}