[BOJ] 15711 : 환상의 짝궁

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

---

에라토스테네스체 소수 골드바흐의추측 정수론

[ 알고리즘풀이 ]

 

 우리는 A + B가 두 소수의 합으로 표현되는지 판단해야된다. ( A + B 를 S 라고 표현하겠다 )

 1) S 가 짝수인 경우

 --> 골드바흐가 짝수인 수는 '2'를 제외하고 모두 두 소수의 합으로 표현이 가능하다고 추측했고, 10^18 이하의 숫자에 대해서는 해당 추측이 참이라고 증명이 됐다.

 --> '2'를 제외하고 S가 짝수인 경우는 두 소수의 합으로 표현 할 수 있다!

 --> '2' 는 두 소수의 합으로 표현이 불가능하다

 

 2) S 가 홀수인 경우

 --> 홀수는 짝수 + 홀수로만 표현이 가능하다. 즉, 짝수 소수 + 홀수 소수로 표현이 가능한지 아닌지 판단하면 된다.

 --> 짝수 소수는 '2' 밖에 없으므로 우리는 ( S - 2 ) 가 소수인지 아닌지 판단하면 된다.

 --> S가 최대 4 * 10^12 이므로 우리는 route(4 * 10^12) 인 2 * 10^6 이하의 소수만 알고있으면 S가 큰 값이 들어오더라도 소수인지 아닌지 판단이 가능하다.

 --> 따라서 에라토스테네스 체를 이용해 2 * 10^6 이하의 소수들을 다 구해놓고 ( S - 2 ) 가 2 * 10^6 보다 작다면 에라토스테네스 체로 바로 소수인지 판단하고, 2 * 10^6 보다 크다면 에라토스테네스 체로 구해놓은 소수들로 다 나누어보면 된다.

 

[ C++ 코드구현 ]

#include<iostream>
#include<vector>
 
using namespace std;
 
const int MAX_LENGTH = 2000000;
vector<int> prime;
bool eratos[MAX_LENGTH + 1];
 
void eratosthenes(void) { // 에라토스테네스체로 2백만 이하의 모든 소수를 구하자 false면 소수
    eratos[0] = eratos[1] = true;
    for (int i = 2; i <= MAX_LENGTH; i++) {
        if (eratos[i] == false) {
            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::sync_with_stdio(false);
    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 { // S가 홀수라면 --> 짝수 + 홀수 꼴만 가능 --> 짝수 소수는 2 밖에 없음
            if (isPrime(S - 2)) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ15711.cpp

travelbeeee/ProblemSolving

---