백준 15711번 환상의 짝꿍 c++ 풀이

문제

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

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

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

입력

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

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

출력

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

예제 입력 1 복사

2
3 4
3 5

예제 출력 1 복사

YES
YES

 

에라토스테네스의 체 문제이다.

문제에서 2 * 10의 12승 까지 정수가 주어진다고 해서 고민을 했는데 다른 코드를 참고하니 어차피 두수의 절반을 나누기 때문에 (4 * 10의 12승)의 절반인 2 * 10의 6승까지만 에라토스테네스의 체로 소수를 구하면 된다고 한다.

 

따라서 먼저 에라토스테네스의 체로 소수를 2*10의6승까지 구하고

골드바흐의 추측에 따라 짝수라면 소수의 합이기 때문에 YES 출력,

2라면 소수자체이기 때문에 두수의 합이 2가 나온다면 NO 출력,

짝수도 아니고 2도 아니라면 두수의 합이 홀수라는 뜻인데

홀수에서 소수는 짝수 소수와 홀수 소수의 합으로만 이루어진다.

그런데 여기에서 짝수 소수는 2밖에 없기 때문에 문제가 간단해진다.

합에서 짝수 소수인 2를 뺀 값이 무조건 홀수 소수여야 하기 때문에

나머지 값을 isPrime을 통해서 소수인지 아닌지 판단을하고 정답을 출력하면 된다.

 

 

 

- c++

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

const int MAX_LENGTH = 2000000;
vector<int>prime;
bool eratos[MAX_LENGTH+1];

void eratosthenes(){
    eratos[0] = eratos[1] = true;

    for(int i = 2; i<=MAX_LENGTH; i++){
        if(eratos[i]==true)
            continue;
        prime.push_back(i);
        for(int j = i * 2; j<=MAX_LENGTH; j+=i){
            eratos[j]=true;
        }
    }
}

bool isPrime(long long A){
    if(A <= MAX_LENGTH) return !eratos[A];
    else{
        for(int i = 0 ; i < prime.size(); i++){
            if(A%prime[i]==0){
                return false;
            }
        }
        return true;
    }
}


int main(void){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    eratosthenes();

    int T;
    cin >> T;

    while(T--){
        long long A,B,S;
        cin >> A >> B;
        S = A + B;
        if(S==2) cout << "NO" << "\n";
        else if (S%2 == 0) cout << "YES" << "\n";
        else {

            if ( isPrime(S-2) ){
                cout << "YES" << "\n";
            }else{
                cout << "NO" << "\n";
            }
        }
    }
    return 0;
}