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

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

https://pushback.tistory.com/8

소수 문제 해결의 기본

---

 

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

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

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

 

 에라토스테네스의 체를 사용하여 $110,000$ 사이에 있는 모든 소수를 구했다고 가정하자.

 어떤 입력 $n$이 들어왔을 때, 우리는 $x+y=n,(x\le y)$을 만족하는 두 소수 $x,y$가 있다고 가정하면 $x$는 $2\le x\le \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;
}