[BOJ/백준][Gold3] 15711 : 환상의 짝 (C++)

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

15711번: 환상의 짝꿍

 

 

[난이도] Gold3
[유형] 수학

[풀이]
골드바흐의 추측이라는 것을 알고 있어야 해결할 수 있는 문제입니다.

골드바흐의 추측은 2를 제외한 모든 짝수는 두개의 소수로 나타낼 수 있다는 것을 증명한 이론입니다.

즉 문제에서 A+B가 짝수이면서 2가 아니라면 무조건 YES를 출력하면 됩니다.

문제는 홀수인 경우인데, 홀수를 두개의 소수로 나누려면 한쪽은 무조건 짝수가 되어야 하는데

짝수인 소수는 2밖에 없으므로 소수 한개는 2로 확정됩니다.

그러므로 A+B-2 가 소수인지만 판별하면 되는데 이는 에라토스테네스의 체를 이용해

미리 2x10^6까지의 소수를 구해 놓음으로써 판별할 수 있습니다.

 

#include <cstdio>
#include <map>
#include <cmath>
#include <vector>
using namespace std;
using ll = long long;
int T;
ll A,B,np[2000001];
vector<ll> primes;
int main(){
    scanf("%d",&T);

    np[1]=1;
    for(int i=2;i<=2000000;i++){
        if(np[i]) continue;
        for(int j=i*2;j<=2000000;j+=i){
            np[j]=1;
        }
    }
    for(ll i=2;i<=2000000;i++) if(!np[i]) primes.push_back(i);

    while(T--){
        scanf("%lld%lld",&A,&B);
        ll sum = A+B;
        if(sum==2) {
            puts("NO");
            continue;
        }
        if(sum%2){
            sum-=2;
            bool ok=0;
            if(sum<=2000000) {
                puts(np[sum] ? "NO" : "YES");
                continue;
            }
            for(auto p : primes){
                if(sum<p) break;
                if(sum%p==0) {
                    ok=1;
                    break;
                }
            }
            puts(ok?"NO":"YES");
        }else{
            puts("YES");
        }
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/15711.cpp