환상의 짝꿍 (feat. 백준, 15711번)

환상의 짝꿍
https://www.acmicpc.net/problem/15711

15711번: 환상의 짝꿍

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <cmath>
#include <vector>
#define MAX_VALUE   2000000
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    bool arr[MAX_VALUE + 5]{false};
    arr[0] = arr[1] = true;
    register int e = sqrt(MAX_VALUE);
    for(register int i = 2, j; i <= e; ++i)
        if(!arr[i])
            for(j = i << 1; j <= MAX_VALUE; j += i)
                arr[j] = true;
    vector<int> check;
    for(register int i = 2; i <= MAX_VALUE; ++i)
        if(!arr[i])
            check.push_back(i);
    register int T;
    register long long A, B, C;
    cin >> T;
    for(register int t = 0; t < T; ++t){
        cin >> A >> B;
        C = A + B;
        bool passed = false;
        if(C & 1){  // 홀수
            if(C - 2 <= MAX_VALUE){
                if(!arr[C - 2])
                    passed = true;
            }
            else{
                passed = true;
                for(auto& v : check)
                    if((C - 2) % v == 0){
                        passed = false;
                        break;
                    }
                // for(register int i = 2; i <= MAX_VALUE; ++i)
                //     if(!arr[i] && ((C - 2) % i) == 0){        // 소수이고 나눠떨어지면 탈락
                //         passed = false;
                //         break;
                //     }
            }
        }
        else    // 짝수
            if(C > 2)   // 골드바흐의 추측 (2보다 큰 짝수는 두 소수의 합)
                passed = true;
        if(!passed)
            cout << "NO\n";
        else
            cout << "YES\n";
    }
    return 0;
}
// *&)*@*

 

1. 우리는 A+B=C 라고 했을때, C의 값을 다음과 같이 나눌 수 있습니다.
2. C가 짝수인 경우
   - "골드바흐의 추측" 에 의해 2보다 큰 짝수는 두 소수의 합으로 이루어집니다.
3. C가 홀수인 경우
   - sqrt(2 * 2 * 10^12) 보다 작은 경우, C가 홀수가 되기 위해선 짝수+홀수 여야하고 소수 중 짝수는 2밖에 없습니다.
   - sqrt(2 * 2 * 10^12) 보다 큰 경우, C는 소수로 나누어 떨어져서는 안됩니다.