백준] 9020 - 골드바흐의 추측(ACM-ICPC Regionals)

시간 제한 : 2초

메모리 제한 : 256MB

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다. (4 ≤ n ≤ 10,000)

출력

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

소스코드

#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
int main(void)
{
	int T, N;
	vector<bool> arr(10001, true);
	vector<int> sosu;
	cin >> T;
	for (int i = 2; i <= sqrt(10000); i++)
	{
		if (arr[i] == false)
			continue;
		for (int j = i + i; j <= 10000; j += i)
			arr[j] = false;
	}
	for (int i = 2; i <= 10000; i++)
		if (arr[i])
			sosu.push_back(i);

	int size = sosu.size();
	while (T--)
	{
		cin >> N;
		int tmp = 0, max = 10000, ans1, ans2;
		for (int i = 0; i < size; i++)
		{
			if (N - sosu[i] < 0)
				break;
			else if (arr[N - sosu[i]] && (N - sosu[i] * 2 )>=0)
			{
				if (max > (N - sosu[i]*2))
				{
					max = N - sosu[i] * 2;
					ans1 = sosu[i];
					ans2 = N - sosu[i];
				}
			}
		}
		cout << ans1 << ' ' << ans2 << '\n';
	}
}

Tip

에라토스테네스의 체로 소수를 걸러내고 골드바흐 파티션을 만들어나가는 방식으로 푼다. 에라토스테네스의 체에서는 루트 N까지만 탐색하고, 파티션을 구할 때에는 중복해서 파티션을 찾지 않도록 ans1이 ans2보다 작거나 같을 떄까지만 계속 파티션을 찾아나가는 식으로 연산 횟수를 줄일 수 있다.