[백준 알고리즘] 15711번: 환상의 짝꿍

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

문제

문제
환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이어붙이고 그 끈을 다시 길이가 소수인 끈 두개로 정확히 나눌 수 있다면 두 사람은 환상의 짝꿍이라고 한다. 하지만 그들은 길이가 소수인 두개의 끈으로 나눌 수 있는지 판단하는 것이 어려워서 대부분 서로가 인연임을 모르고 그냥 지나간다고 한다. 애석하게도…

그런 그들을 위해서 어떤 두 사람이 환상의 짝꿍인지 판단하는 프로그램을 작성하라.

편의상 두 사람의 끈을 이어붙일 때와 나눌 때 손실되는 끈의 길이는 0이라고 가정한다.

입력
첫째 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 500)가 주어진다.

둘째 줄부터 T개 줄에 두 사람이 가지고 있는 끈의 길이를 나타내는 정수 A, B가 공백으로 구분되어 주어진다. (1 ≤ A, B ≤ 2 × 1012)

출력
각 테스트 케이스마다 한 줄씩 두 사람의 끈을 이어붙이고 그 끈을 다시 길이가 소수인 두개의 끈으로 정확히 나눌 수 있다면 YES, 불가능하면 NO를 출력하라.

풀이

이 문제는 골드바흐의 추측 사용해서 시간을 단축시켜야 하는 문제였다. 골드바흐의 추측은 2를 제외한 모든 짝수는 두 소수의 합을 표현이 가능하다 라는 명제인데, 10^18 이하의 숫자에 대해서는 모두 증명되었다. 따라서 입력으로 들어온 두 숫자의 합이 10^18 이하이고, 짝수라면, 소수를 검사해볼 필요없이 항상 YES 를 출력할 수 있다.

만약 입력으로 들어온 숫자가 홀수일 경우에는 홀수는 항상 짝수와 홀수의 합으로 이루어진다. 라는 명제를 이용해서 짝수와 홀수가 각각 소수인지 확인해 볼 수 있다. 그런데 이미 골드바흐의 추측을 통해 2가 10^18 미만의 짝수 중 유일한 소수임을 알 수 있게 된다. 따라서 입력으로 받은 두 숫자의 합이 10^18 미만일 때는 두 숫자의 합 - 2 가 소수인지만 확인해보면 된다.

우리가 입력으로 받는 A와 B의 최대 크기는 2 * 10^12 이고, 두 입력의 합의 최대 크기는 4 * 10^12 이므로, 에라토스테네스의 체를 이용해서 sqrt(4 * 10^12) 인 2*10 ^ 6 = 2000000 에 대한 소수를 미리 구해두고, 두 숫자의 합 - 2 가 2000000 이하일 경우는 미리 구해둔 소수로 판별, 이상일 경우에는 2000000 이하의 모든 소수들로 나누어 보아서 소수인지 확인한다.

문제를 풀 때, 메모리를 아끼려고 에라토스테네스의 체를 bool 배열에 표현두고 index를 숫자로 사용했는데 계속 시간초과가 났다. 소수를 뽑아서 배열에 담아두고 사용하는 것이 시간을 더 효율적으로 쓰는 방법이다.

코드

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

const int MAX = 2000000;
vector<bool> primes(MAX+1, true);
vector<int> primeNums;

bool isPrime(long long int target){
    if(target <= MAX) return primes[target];
    for (int i = 0  ; i < primeNums.size() ; i++){
        if (target % primeNums[i] == 0){
            return false;
        }
    }
    return true;
}

int main (){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int T;
    cin >> T;

    primes[0] = primes[1] = false;
    for(int i = 2 ; i <= sqrt(MAX) ; i++){
        for (int j = i+i ; j <= MAX ; j += i){
            primes[j] = false;
        }
    }

    for (int i = 0 ; i < MAX ; i++){
        if(primes[i]) primeNums.push_back(i);
    }

    while(T--){
        long long int A, B;
        cin >> A >> B;
        long long int sum = A + B;

        if (sum < 4) cout << "NO\n";
        else if (sum % 2 == 0) cout << "YES\n";
        else if(isPrime(sum - 2)) cout << "YES\n";
        else cout << "NO\n";
    }

}