골드바흐 파티션_ 백준 17103

골드바흐 파티션은 이전에 풀었던 골드바흐의 추측과 관련된 문제입니다.

 

2020/05/17 - [백준 문제풀이] - 골드바흐의 추측 _ 백준 6588

 

---

골드바흐의 추측은 2보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 라는 추측이다.

이번 문제는 이 골드바흐의 추측을 기반으로 짝수 N을 두 소수의 합으로 나타내는 골드바흐 파티션을 구하는 문제이다.

여기서 두 소수의 순서만 다른 것은, 같은 파티션으로 취급한다.

 

에라토스테네스의 체를 활용하여 소수를 먼저 확인해놓고, 그 뒤에 결과값을 출력하는 형식으로 알고리즘을 짜면 된다.

 

골드바흐 파티션을 계산할 때, '두 소수의 순서만 다른 것은, 같은 파티션으로 취급한다.'라는 조건에 따라 해당 값을 반으로 나눈 값까지만 세면 된다. 

 

코드는 다음과 같다.

#include <iostream>
#include <cstdio>

#define MAX 1000000
using namespace std;

bool check[MAX + 1];
int prime[MAX];
int pn = 0;

int main(void)
{
    check[0] = check[1] = true;
    for (int i = 2; i < MAX; i++) // 에라토스테네스의 체 
    {
        if (check[i] == false)
        {
            prime[pn++] = i;
            for (int j = i * 2; j < MAX; j += i)
                check[j] = true;
        }
    }

    int num;
    scanf("%d", &num);

    while (num--)
    {
        int a;
        int result = 0;

        scanf("%d", &a);

        for (int i = 0; prime[i] * 2 <= a; i++) // 절반값까지 result를 센다
        {
            if ((check[a - prime[i]]) == false)
            {
                result++;
            }
        }

        printf("%d\n", result);
    }
    return 0;
}