환상의 짝꿍 15711

문제

접근 방법

처음에는 합에다가 소수인 수로 뺀 뒤 소수인지 확인해보는 방법을 사용해보려 했다.
하지만 두 수의 합의 범위가 2~ 4 × 10^12이고 테스트 케이스가 500개가 되니 소수를 재활용하는 방법으로 가야 한다고 생각했다.

코드

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#define MaxN 2000000 // 2*10^12*2의 제곱근
using namespace std;
typedef unsigned long long ull;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;
    vector<int> prime;
    bool isPrime[MaxN + 1];
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (ull i = 2; i <= MaxN; ++i)
    {
        if (isPrime[i])
        {
            prime.push_back(i);
            for (ull j = i * i; j <= MaxN; j += i) // i의 배수들은 소수가 아니다.
            {
                isPrime[j] = false;
            }
        }
    }
    while (T--)
    {
        bool isAble = true;
        ull A, B, sum;
        cin >> A >> B;
        sum = A + B;
        if (sum <= 3) // 3 이하는 소수 + 소수가 불가능하다.
        {
            isAble = false;
        }
        else if ((sum & 1) == 0) // 골드 바흐 추측으로 2 이상의 짝수는 소수 + 소수가 가능하다.
        {
            isAble = true;
        }
        else // 2보다 큰 홀수에서 가능한 것은 2 + 소수의 모양이다.
        {
            sum -= 2;
            for (int p : prime)
            {
                if (sum == p) // 합-2와 소수가 같으면 탈출하면 된다.
                {
                    break;
                }
                if (sum % p == 0) // 소수로 나눠지면 소수가 아니다.
                {
                    isAble = false;
                    break;
                }
            }
        }
        cout << (isAble ? "YES" : "NO") << '\n';
    }
}

풀이

에라토스테네스의 체라는 방법을 사용하면 특정 범위의 소수 목록을 저장해둘 수 있다. 소수인지 확인해줄 소수 목록을 저장해둔다.

3 이하의 합에서는 소수가 나올 수 없으니 소수가 아니다.
골드바흐 추측으로 2 이상의 짝수는 소수 + 소수의 모양으로 나눌 수 있다.
2보다 큰 홀수에서 가능한 것은 2 + 소수의 모양이다.
왜냐하면 홀수는 짝수 + 홀수의 형태로 나눌 수 있는데 짝수 중에 소수는 2이기 때문이다. 나머지 홀수가 소수가 맞는지 확인해보면 된다.

에라토스테네스의 체를 실제로 사용해본 것과 골드바흐 추측에 대해서 알아갈 수 있는 문제였다.