[C++] 백준 17103: 골드바흐 파티션

<풀이>

 

사실 이 문제의 풀이라기 보다는 이 문제에서 무조건 이용해야하는 에라토스테네스의 체 에 대한 풀이이다.

 

소수 관련 문제인데 시간제한이 타이트하면 무조건 에라토스테네스의 체를 생각하면 된다. 이 문제도 에라토스테네스의 체를 이용해서 풀어야 한다.

 

에타로스테네스의 체는 원하는 숫자의 범위 내에 소수를 판별할 수 있는 가장 빠른 방법이다. 가령 [1, 100] 범위 안의 소수를 알고 싶다면, 1에서 100까지의 숫자를 나열한 후 2의배수, 3의배수, 5의 배수, 7의 배수, ... , 10의 배수(100의 제곱근)에 대해서는 소수가 아니라고 표시하면 된다. 4의 배수, 6의 배수, 8의 배수, 9의 배수는 앞에서 2의배수, 3의배수에서 모두 아니라고 표시되므로 굳이 안해줘도 된다. 

 

좀 더 일반적으로 정의하면 1에서 MAX까지의 소수에 대해 판별하고 싶으면 1에서 MAX까지의 수를 나열한 후, 2의 배수부터 MAX 제곱근의 배수에 대해 소수가 아니라고 표시하면 된다.

 

이 문제에서는 MAX가 1000000 이므로 1부터 1000까지의 배수에 대해 소수가 아니라고 표시하면 되며 이는 배열로 간단히 구현할 수 있다. 나머지 부분은 간단하므로 설명을 생략한다.

 

<소스코드>

#include <iostream>
#include <cmath>

int main() {

    int* num = new int[1000001] { 0 }; //소수면 0, 소수가 아니면 1의 값을 가지게 함 

    num[0] = 1;
    num[1] = 1;

    int range = int(std::sqrt(1000000));

    for (int i = 2; i <= range; i++) { //에라토스테네스의 체
        if (num[i] == 1)
            continue;
        else {
            for (int j = 2 * i; j <= 1000000; j += i) {
                num[j] = 1;
            }
        }
    }

    int t; // test case
    std::cin >> t;
    
    int n; // even num
    int p_num = 0; // 파티션 넘버

    for (int c = 0; c < t; c++) {
        std::cin >> n;

        for (int i = 1; i <= n / 2; i++) {
            if (num[i] != 0) // i가 소수가 아니면 넘어감
                continue;
            else { //i가 소수일 때
                if (num[n - i] == 0)
                    p_num++;
            }
        }
        std::cout << p_num << "\n";
        p_num = 0;
    }

    delete[] num;
}