[백준][수학]골드바흐의 파티션

17103번: 골드바흐 파티션

짝수 N을 두 소수의 합으로 나타낼 때 N에 대한 두 소수의 합의 개수를 출력하는 문제. 기존에 풀었던 골드바흐의 추측에서 작성한 코드를 이용하면 쉽게 풀 수 있다.

#include <iostream>
using namespace std;
 
const int Max = 1000000;
bool arr[Max + 1];
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    arr[0] = arr[1] = true;
    for (int i = 2; i * i < Max; i++)
    {
        if (arr[i] == false)
        {
            for (int j = i + i; j <= Max; j += i)
                arr[j] = true;
        }
    }
 
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int count = 0;
        for (int i = 2; i <= n/2; i++) // 순서만 다른 것을 count하지 않기 위해 i<=n/2
        {
            if (arr[i] == false && arr[n - i] == false)
                count++;
        }
        cout << count << '\n';
    }
    return 0;    
}

 

골드바흐의 추측