[Algorithm] Baekjoon 17103번 : 골드바흐 파티션

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
int t, n;
bool isPrimeNum[1000001] = { false };
 
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    memset(isPrimeNum, true, sizeof(isPrimeNum));
 
    isPrimeNum[0] = isPrimeNum[1] = false; // 0,1은 소수가 아님.
 
    for (int i = 2; i*i < 1000000; ++i)
    {
        if (!isPrimeNum[i]) continue;
 
        for (int j = i + i; j <= 1000000; j += i)
        {
            isPrimeNum[j] = false;
        }
    }
 
    cin >> t;
 
    while (t--)
    {
        cin >> n;
 
        int answer = 0;
 
        for (int i = 2; i <= n / 2; ++i)
        {
            if (isPrimeNum[i] && isPrimeNum[n - i])
            {
                ++answer;
            }
        }
 
        printf("%d\n", answer);
    }
}
 
 

 

주어지는 수가 소수 두개로 조합되는 경우의 수를 구하는 문제인데, 숫자가 주어지는 테스트케이스는 100개라서 미리 어떤수가 소수인지를 구해놔야 한다.

유명한 에라토스테네스의 체를 이용해서 구했으며, 이후 주어지는 숫자마다 n/2까지 검사해서 두 숫자가 소수면 답을 카운팅해주면 된다.