백준 15711 (환상의 짝꿍) / C++

문제 링크 : 15711번: 환상의 짝꿍 (acmicpc.net)

15711번: 환상의 짝꿍

> 풀이

 

두 수를 합치면 최대 4 * 10^12입니다. 에라토스테네스의 체를 사용하여 제곱근인 2 * 10^6 까지의 소수들을 찾아 이 소수들을 활용하여 답을 구해나갑니다.

 

두 수를 합쳤을 때 짝수라면 무조건 소수의 합으로 나타낼 수 있습니다. (골드바흐의 추측)

두 수를 합쳤을 때 홀수라면 2 + 홀수로 나타내는 경우가 아니라면 불가능합니다.

 

#include <bits/stdc++.h>
using namespace std;

long long A, B, S;
int T;
bool prime[2000001];
vector<int> v;

int main(void)
{
        prime[1] = 1;
        for (int i = 2; i * i < 2000000; i++) {
                if (!prime[i])
                        for (int j = i * i; j < 2000000; j += i)
                                prime[j] = true;
        }

        for (int i = 2; i <= 2000000; i++)
                if (!prime[i])
                        v.push_back(i);

        scanf("%d", &T);
        while (T--) {
                scanf("%lld %lld", &A, &B);
                S = A + B;

                if (S == 2 || S == 3) {
                        printf("NO\n");
                }
                else if (S % 2 == 0) {
                        printf("YES\n");
                }
                else {
                        S -= 2;
                        bool check = false;
                        for (int i = 0; i < v.size() && (long long)v[i] * v[i] <= S; i++)
                                if(S % v[i] == 0) {
                                        printf("NO\n");
                                        check = true;
                                        break;
                                }
                        if (!check) printf("YES\n");
                }
        }
        return 0;
}