백준 알고리즘 17103번 : 골드바흐 파티션

Zoo Da·2021년 6월 16일

백준 알고리즘

목록 보기

83/337

링크

https://www.acmicpc.net/problem/17103

문제

골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.
짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

출력

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

예제 입력 및 출력

풀이법

시간 제한이 0.5초라서 루트를 사용한 소수를 구하는 방법이 아닌 에라토스테네스의 체를 구현해서 사용하였다.
MAX만큼의 소수를 저장하는 배열을 만들고 에라토스테네스의 체를 사용해서 소수들만 배열에 저장시킨다.
그 후에 문제에서 제시한 대로 테스트 케이스를 입력 받고 반복문을 돌려서 문제에서 제시한 조건을 통해 문제를 해결하면 된다.
이 때 두 소수의 순서만 다른 것은 같은 파티션이다라고 하였는데 예외처리를 해주기 위해서 계속 고민했지만 답이 보이지 않아서 그냥 서로 같은 수일때의 경우를 한번 더 세어주고 결과값을 2로 나누어 주는 방식으로 계산하였다.

풀이 코드

// 17103번 : 골드바흐 파티션

#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#define MAX 1000001

int primeNumber[MAX];

// 에라토스테네스의 체 사용
void clearArray()
{
    for (int i = 2; i < MAX; i++)
    {
        primeNumber[i] = i;
    }
}

void setUpPrimeNumber()
{
    clearArray();
    for (int i = 2; i < MAX; i++)
    {
        if (primeNumber[i] == 0)
            continue;
        for (int j = i + i; j < MAX; j += i)
        {
            primeNumber[j] = 0;
        }
    }
}

int main()
{
    int t;
    scanf("%d", &t);
    setUpPrimeNumber();
    while (t--)
    {
        int x;
        scanf("%d", &x);
        int a;
        int sum = 0;
        for (int i = 2; i <= x; i++)
        {
            a = i;
            if (x == (primeNumber[a] + primeNumber[x - a]))
            {
                sum++;
                if (primeNumber[a] == primeNumber[x - a])
                {
                    sum++;
                }
            }
        }

        printf("%d\n", sum / 2);
    }
    return 0;
}