BOJ 17103 골드바흐 파티션

1 개요

BOJ 17103 골드바흐 파티션

• 백준 온라인 저지 17103번 문제
• BOJ 15단계

2 C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T, n, cnt, i, j;
    int arr[1000001] = {0};
    for(i=2; i<1000001; i++) {
        arr[i] = i;
    }
    for(i=2; i*i<1000001; i++) {
        for(j=i*i; j<1000001; j+=i) {
            arr[j] = 0;
        }
    }

    cin >> T;
    for(i=0; i<T; i++) {
        cin >> n;
        cnt = 0;
        for(j=2; j<n; j++) {
            if(arr[n-j]+arr[j] == n) {
                cnt++;
                if(n-j==j) cnt++;
            }
        }
        cout << cnt / 2 << "\n";
    }
}