C++ 알고리즘 - 백준 17103 골드바흐 파티션 (에라토스테네스의 체)

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

 

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

int prime[1000002];

void CPP_INIT() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

int main(void) {
	CPP_INIT();

	for (int i = 2; i < 1000002; i++) {
		prime[i] = i;
	}

	for (int i = 2; i <= sqrt(1000002); i++) {
		if (prime[i] == 0) continue;

		for (int j = i * i; j <= 1000002; j += i) {
			prime[j] = 0;
		}
	}

	int input;
	int num;

	cin >> input;

	for (int i = 0; i < input; i++) {
		cin >> num;

		int a =  num / 2;
		int b = num / 2;

		int cnt = 0;

		while (a > 1) {
			if (prime[a] + prime[b] == num) cnt++;

			a--;
			b++;
		}

		cout << cnt << endl;
	}
}