BOJ 15711 : 환상의 짝꿍

• 문제 링크 : boj.kr/15711
• 난이도 : G3
• 태그 : 정수론, 소수 판정

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

vector<ll> sieve(int n) {
    vector<ll> primes;
    vector<bool> check(n+1, true);
    for(int i = 2; i <= n; i++) {
        if(check[i]) {
            primes.emplace_back(i);
            for(int j = i+i; j <= n; j += i) {
                check[j] = false;
            }
        }
    }
    return primes;
}

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

    int T;
    cin >> T;
    vector<ll> primes = sieve(2e6);
    while(T--) {
        ll a, b;
        cin >> a >> b;
        a += b;
        if(a < 4) {
            cout << "NO\n";
            continue;
        }
        if(a % 2) {
            bool check = true;
            a -= 2;
            for(auto u : primes) {
                if(a != u && a % u == 0) {
                    check = false;
                    break;
                }
            }
            cout << (check ? "YES" : "NO") << "\n";
        }
        else {
            cout << "YES" << "\n";
        }
    }
    return 0;
}

---

풀이

a+b의 합을 두 소수의 합으로 나타낼 수 있는지 확인한다.

두 소수의 합과 관련된 유명한 추측이 있다. 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다는 골드바흐의 추측은 400경 이하의 짝수에서 성립함이 확인되었으므로 a+b가 짝수라면 두 소수의 합으로 나타낼 수 있다.

a+b가 홀수라면 가능한 경우는 2 + x꼴이므로 x가 소수인지 확인하면 된다. x가 4*10^12보다 작으므로 2*10^6까지의 소수로 나눠보면 된다.