[C++] 백준 17103. 골드바흐 파티션

문제

골드바흐씨 생각엔 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있고, 짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다.

T(1~100)개의 짝수 N(2~1,000,000)이 주어질 때,
골드바흐 파티션의 개수를 출력하는 문제이다.
소수의 순서만 다른 건 같은 파티션으로 친다.

풀이

입출력 예제를 확인해보니 3 + 3 = 6도 된다.
즉, 같은 소수 두 개를 쓸 수 있다.

기본적으로 두 수의 합이 N이 되게 만드는 거니까
N보다 작은 모든 소수를 도는 게 아니라,
N의 절반까지만 확인하는 식으로 풀었다.

코드

#include <iostream>
#include <vector>
using namespace std;

int t, n;
vector<bool> v(1000000, true);

void getPrime() {
	v[0] = false;
	v[1] = false;
	for (int i = 2; i < 1000000; i++) {
		if (v[i]) {
			for (int j = i * 2; j < 1000000; j += i) {
				v[j] = false;
			}
		}
	}
}

void goldbach() {
	int cnt = 0;
	for (int i = 2; i <= n / 2; i++) {
		if (v[i] && v[n - i]) cnt++;
	}
	cout << cnt << "\n";
}

int main() {
	getPrime();
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		goldbach();
	}

	return 0;
}

채점

야호