17103번: 골드바흐 파티션 [C++]

문제

 

 

풀이

 주어질 수 있는 n의 최댓값이 1000000이므로 arr[1000001]을 선언하고 arr[i] = i가 되도록 채워준다.

이후 에라토스테네스의 체 방법을 이용해 소수가 아닌 수들을 걸러낸 후 더해서 n이 될 수 있는 두 소수들을 구한다. 두 소수가 같다면 cnt++을 한 번 더 해주고 cnt를 2로 나눈 몫을 리턴한다.

#include <iostream>

using namespace std;

int arr[1000001] = { 0, };

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL);
    
    int t, n;

    for (int i = 2; i <= 1000000; i++)
        arr[i] = i;

    for (int i = 2; i * i <= 1000000; i++) {
        if (arr[i] == 0) continue;

        for (int j = i * i; j <= 1000000; j += i)
            arr[j] = 0;
    }

    cin >> t;

    for (int i = 0; i < t; i++) {
        int cnt = 0;

        cin >> n;

        for (int j = 2; j < n; j++) {
            if (arr[n - j] + arr[j] == n) {
                cnt++;

                if (n - j == j)
                    cnt++;
            }
        }

        cout << cnt / 2 << "\n";
    }

	return 0;
}