6588, 15711 백준

문제

문제 분석

입력 a,b에 대하여 a+b를 2개의 소수로 나눌 수 있는가?를 묻는 질문이다.

다른 쉬운 소수 문제와는 별개로 범위가 1 ≤ A, B ≤ 2 × 10^12 로 꽤 크다는 점이다.

가장 먼저 생각해본 방법은 에라토스테네스의 체를 이용하여 하나의 소수, a'를 얻고 sum - a'인 b'를 sqrt(b')까지 나눠가면서 b'가 소수인지 판별하는 방법이었다. 하지만 문제 조건에 의하면 에라토스테네스의 체를 이용해서 얻을 수 있는 범위가 그래봐야 10^8이고 그렇게 되면 b의 범위는 10^12정도가 되므로 10^4초가 걸리게 되면서 시간 초과가 날 것 같아 다른 방법을 고안하였다.

그래서 이전에 풀었던 6588번 골드바흐의 추측 문제를 떠올렸는데 이 추측에 따르면

"4보다 큰 모든 짝수들은 두개의 소수합으로 나타낼 수 있다" 라는 것이었는데, 이 추측이 아직까지 증명되지 않았지만 현재 밝혀진 모든 값에 대하여 만족하기 때문에 이것이 참이라고 여겨진다고 한다.

그렇다면 참이라고 여겨지는 이 추측에 의하여 4보다 큰 모든 짝수는 두개의 소수합으로 나눌 수 있을 것이다.

 1과 2와 3은 소수의 정의에 의하여 2개의 소수합으로 나타낼 수 없고 문제는 5이상의 홀수를 소수합으로 나타낼 수 있는지 판별하는 문제가 남아있는데, 2를 제외한 모든 소수는 홀수이므로 (짝수라면 2로 나눠지므로 소수가 아니기 때문에) 소수 2개의 합이 홀수가 되는 경우의 수는 "소수 + 2" 뿐이다.

따라서 Sum - 2 그 자체가 소수인지 판별하는 쉬운 문제로 변환되는데 이 과정에서 2부터 sqrt(sum-2)까지 sum-2를 나눠서 나머지 값을 확인하는 방식으로 그 수가 소수인지 확인하려고 하였으나 시간초과가 났다.

그 이유에 대해서 분석해보자면 500 * sqrt(2*2*10^12) = 500 * 2*10^6 = 10^9 이기 때문에 약 10초의 시간이 걸리기 때문이었을 것이다.

그래서 나는 정말 맨붕에 빠졌다. 왜냐하면 그 범위는 메모리에 담기 어려울만큼 큰 범위이고 이 방식이 메모리를 사용하지 않고 소수를 판별하는 가장 최소복잡도를 갖는 방식이었기 때문이었다.

하지만 에라토스테네스의 체를 이용하여 이를 해결할 수 있었는데 그 스텝은 다음과 같았다.

0. 소수는 1과 자신으로만 나눠지는 수이다

1. 하나의 수를 두 수의 곱으로 나눌 때 각 약수들의 범위는 1~sqrt(n)이다. (sqrt(n)^2 = n)

2. 1~sqrt(n)의 모든 수는 1~sqrt(n)사이의 소수들로 표현할 수 있다.

이렇기 때문에 에라토스테네스의 체를 이용하여 1~sqrt(n)까지의 모든 소수를 찾고 그 모든 소수들에 대해서 sum이 나누어 떨어지지 않는다면 그 수는 소수일 것이라는 것이다.

에라토스테네스의 체를 단순히 범위 내의 소수를 찾는 방식이므로 그 범위가 메모리 제한을 넘어가면 못쓴다는 상식을 벗어나게 해주고 사고를 유연하게 가져야 함을 느끼게 해준 문제였다

코드

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<vector>
#include<stack>
#include<queue> // priority_queue 포함
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>

#include<algorithm>
#include<math.h>
#include<climits> // 자료형 limit포함

using namespace std;

typedef long long int lld;
typedef unsigned long long int uld;
typedef unsigned int ui;

const int MY_INT_MAX = 2000000000;
vector<int> prime_v;
bool check_arr[2000001] = {0};

bool is_prime(lld now_val)
{
    lld sqrt_val = (lld)sqrt(now_val)+1;
    lld now_limit = lower_bound(prime_v.begin(), prime_v.end(), sqrt_val) - prime_v.begin();
    if(now_limit == prime_v.size())
        now_limit--;
    for(lld i=0; i<=now_limit; i++)
    {
        if(now_val % prime_v[i] == 0)
            return false;
    }
    return true;
}

void solution()
{
    int n;
    cin >> n;
    vector<pair<lld,lld>> input_v;
    lld my_max = 2;
    for(lld i=0; i<n; i++)
    {
        lld a,b;
        cin >> a >> b;
        input_v.push_back(make_pair(a,b));
        my_max = max(my_max, a + b);
    }
    lld limit_val = (lld)sqrt(my_max) + 1;
    for(lld i=2; i<=limit_val; i++)
    {
        if(check_arr[i] == 0)
        {
            prime_v.push_back(i);
            lld tmp_counter = 2;
            while(i*tmp_counter <= limit_val)
            {
                check_arr[i*tmp_counter] = 1;
                tmp_counter++;
            }
        }
    }
    for(lld i=0; i<n; i++)
    {
        lld now_sum = input_v[i].first + input_v[i].second;
        if(now_sum < 4)
            cout << "NO\n";
        else if(now_sum % 2 == 0)
                cout << "YES\n";
        else
        {
            if(is_prime(now_sum - 2))
                cout << "YES\n";
            else
                cout << "NO\n";
        }
    }
}

int main ()
{
    iostream::sync_with_stdio(0); // 이제 C stdio의 입출력 사용 불가
    cin.tie(NULL);
    cout.tie(NULL); // 개행도 \n로 하도록 하자.
    solution();
    return 0;
}

 

개선점?

유연한 사고, 수학적 지식의 응용 요망!