[백준] 15711번 : 환상의 짝꿍 (C++)

15711번 : 환상의 짝꿍

---

문제)

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

 

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

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

 

 

 

입력 :

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

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

 

 

 

출력 :

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

 

 

 

 

 

 

 

풀이)

 

// 15711. 환상의 짝꿍
#include <iostream>
#include <vector>
 
using namespace std;
 
bool prime[2000011];
vector<int> primeNumber;
 
// A + B의 최대 값은 4,000,000,000,000
// 이 수는 최대 2,000,000까지 약수로 가질 수 있고,
// 2,000,000까지의 소수로 (A + B - 2)가 나눠지지 않는다면,
// 해당 수는 소수임이 확실하다.
void isPrime()
{
    prime[1] = true;
 
    for (long long i = 2; i <= 2000010; i++)
    {
        if (prime[i]) continue;
 
        for (long long j = i * i; j <= 2000010; j += i)
        {
            prime[j] = true;
        }
    }
 
    for (int i = 1; i < 2000010; i++)
    {
        if (prime[i] == false) primeNumber.push_back(i);
    }
}
 
 
int main()
{
    int t;
    cin >> t;
    
    isPrime();
 
    long long a, b;
    while (t--)
    {
        cin >> a >> b;
 
 
        if ((a == 1 && b == 1) || (a + b == 3)) cout << "NO\n";
        // 둘 다 홀수인 경우 -> 짝수
        else if (a % 2 && b % 2) cout << "YES\n";
        // 둘 다 짝수인 경우
        else if (a % 2 == 0 && b % 2 == 0) cout << "YES\n";
        
        // 둘 중 하나가 홀수인 경우.
        // 2 + 홀수로 표현되어야 한다.
        else
        {
            long long temp = a + b - 2;
 
            bool flag = false;
            for (int i = 0; i < primeNumber.size(); i++)
            {
                if (primeNumber[i] >= temp) break;
                if (temp % primeNumber[i] == 0)
                {
                    flag = true;
                    break;
                }
            }
 
            if (flag) cout << "NO\n";
            else cout << "YES\n";
        }
    }
 
    return 0;
}

---

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

15711번: 환상의 짝꿍