문제 링크

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

문제

풀이

\//시작 15:55
//끝 16:24

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

int main() {
	vector<pair<int, int>> result;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int number[MAX] = { 0 }; //소수 찾기에 사용되는 배열
		int index[MAX] = { 0 }; //소수를 담을 배열
		int num; //입력받은 숫자
		cin >> num;
		//에라토스테네스의 체를 이용하여 소수 찾기
		int cnt = 0;
		for (int j = 2; j < num; j++) {
			if (number[j] == 0) {
				index[cnt] = j; //찾은 소수를 담음
				cnt++; //소수 배열의 크기를 알기 위한 변수
				int multi = 2;
				for (int k = j * multi; k < num; k = j * multi) {
					number[k] = 1;
					multi++;
				}
			}
		}

		//골드바흐 파티션 찾기
		int g_1; //파티션 중 작은 값
		int g_2; //파티션 중 큰 값
		for (int i = 0; i < cnt; i++) {
			int a = index[i]; //찾은 소수 배열에서 작은 수부터 하나씩 꺼냄
			int b = num - a; //찾은 소수에 대응되는 쌍 예측
			if (a > b) { //대응되는 값이 더 작으면 멈춤
				break;
			}
			else { //대응되는 값이 더 큰 경우
				if (number[b] == 0) { //대응되는 값이 소수인 경우 파티션 값 업데이트
					g_1 = a;
					g_2 = b;
				}
			}
		}
		result.push_back(make_pair(g_1, g_2)); //최종 파티션 값 결과 벡터에 저장
		
	}
	//결과 벡터 출력
	for (int i = 0; i < result.size(); i++) {
		cout << result[i].first << " " << result[i].second << '\n';
	}

	return 0;

1. 에라토스테네스를 이용하여 소수를 찾고 따로 배열에 저장한다.
2. 소수가 저장된 배열의 앞에서부터 차례로 대응되는 숫자를 예측한다.
3. 대응되는 숫자가 소수라면 골드바흐 파티션 값으로 업데이트 한다.
4. 대응되는 숫자가 더 작다면 멈춘다.

소수인지 판단하는 방법은 에라토스테네스의 체 배열에서 값이 0인 것으로 판단한다.