환상의 짝꿍 C++ - 백준 15711

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

정수론 문제.

기본 지식

골드바흐의 강한 추측 : 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

에라토스테네스의 체

소수 판별법 중 하나 :

어떤 수 $N$에 대하여 $\sqrt N$까지만 확인해 보면 된다. 관련 글

문제 접근

$A+B=S$에 대해 $S$가 4보다 큰 짝수라면 두 소수의 합으로

나타낼 수 있다.

홀수의 경우를 살펴보자.

홀수는 짝수 + 홀수 형태로 이루어져있다.

따라서 홀수는 나눌 때에 짝수 하나 홀수 하나로 나누어야 한다.

그런데 짝수이면서 소수는 2밖에 없으므로

홀수 $S-2$의 소수 판별만 해주면 된다.

2보다 크거나 같은 자연수는 항상 소수를 인수를 가지고 있으므로,

소수 판별 시 테스트 케이스 시간 초과를 고려한 에라토스테네스의 체를

사용하여 소수 판별을 해준다.

코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
#define MAX 2e6
using namespace std;

bool pnum[(int)MAX+1]={0,};
vector<int> primes;
int t;

void eratosthenes(){
    for(int i=2;i<=(int)MAX;i++){
        if(pnum[i]) continue;
        primes.push_back(i);
        for(int j=i*2;j<=MAX;j+=i) pnum[j]=true;        
    }
}

void solve(){
    ll A,B,S;
    cin >> A >> B; S=A+B;
    if(S<=3) cout << "NO";
    else if(S%2==0) cout << "YES";
    else{
        S-=2;
        bool b=true;
        if(S>MAX){
            for(int i=0;i<primes.size();i++){
                if(S%primes[i]==0) b=false;
            }
        }
        else if(pnum[S]) b=false;

        if(b) cout << "YES";
        else cout << "NO";
    }
    cout << '\n';
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    eratosthenes();
    cin >> t;
    while(t--) solve();
    return 0;
}