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

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

17103번: 골드바흐 파티션

---

문제 풀이

 에라토스테네스의 체를 이용해서 소수들을 정의하고 2부터 입력받은 값(N)의 반까지 경우를 모두 따진다.

느낀 점

 예전의 소수 문제들과 비슷해서 바로 풀어봤는데 그 당시에는 시간제한이 널널해서 에라토스테네스의 체를 사용하지 않았는데 이번엔 0.5초 제한으로 안 쓸 수가 없었다. 이번 기회로 알고리즘을 다시 정리한 계기가 되었다.

 에라토스테네스의 체

시간복잡도 : O(NloglogN) / 2부터 시작해서 자신을 제외한 배수는 모두 지운 나머지는 소수

코드

#include <iostream>
#include <vector>
#define MAX 1000001
using namespace std;

bool prime[MAX] = { 0, };
vector<int>v;

void set_Prime() {
	for (int i = 2;i < MAX;i++) {
		prime[i] = true;
	}
	for (int i = 2; i < MAX;i++) {
		if (!prime[i]) continue;
		for (int j = i + i;j < MAX;j += i) {
			prime[j] = false;
		}
	}
}

int partition(int n) {
	int cnt = 0, mid = n / 2, idx = 2;
	while (idx <= mid) {
		if (prime[idx] && prime[n - idx]) cnt++;
		idx++;
	}
	return cnt;
}

int main() {
	set_Prime();
	int T, n;
	cin >> T;
	for (int i = 0; i < T;i++) {
		cin >> n;
		v.push_back(partition(n));
	}

	for (int i = 0; i < T;i++) {
		cout << v[i] << "\n";
	}

}