백준 9020 - 골드바흐의 추측

문제 번호: 9020

문제 제목: 골드바흐의 추측

문제 주소: https://www.acmicpc.net/problem/9020

문제 내용

어떤 짝수에 대해 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다.
입력된 짝수 n의 골드바흐 파티션을 출력한다. 골드바흐 파티션이 여러가지 일 경우 두 소수의 차이가 가장 작은 것을 출력한다.

테스트 케이스

3 8 10 16

3 5 5 5 5 11

문제 풀이

두 소수의 차이가 가장 적은 경우를 출력하는 것이므로 증가식보다는 감산식으로 하는 편이 빠르다.
실제로 증가식으로 했을 때는 12ms 소요되던 시간이 감산식으로 할 경우 0ms로 감소하는 것을 볼 수 있다.
1. 에라토스테네스의 체를 통해 10000 이하의 소수를 식별한다.
2. n을 입력 받는다.
3. n / 2부터 시작하여 감산식으로 현재 수 i가 소수이고, n - i도 소수인 경우를 찾는다.
4. 3이 성립하는 숫자를 출력하고 반복문을 빠져나온다.
※ 소수는 2를 제외하고 모두 홀수로 구성되어 있다. 따라서 4를 제외한 나머지 짝수는 모두 홀수의 합으로 표현된다.

풀이 코드

#include <iostream>
using namespace std;

void BAEKJOON_9020()
{
	bool primeArr[10001] = { false };
	for (int j = 4; j <= 10000; j += 2)
	{
		primeArr[j] = true;
	}
	for (int i = 3; i <= 10000; i += 2)
	{
		for (int j = i * 3; j <= 10000; j += i * 2)
		{
			primeArr[j] = true;
		}
	}

	int T;
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		int n;
		cin >> n;
		if (n == 4)
		{
			cout << 2 << ' ' << 2 << endl;
		}
		else
		{
			int currentNumber = (n / 2) % 2 != 0 ? n / 2 : n / 2 - 1;
			while (currentNumber > 0)
			{
				if (!primeArr[currentNumber] && !primeArr[n - currentNumber])
				{
					cout << currentNumber << ' ' << n - currentNumber << endl;
					break;
				}
				currentNumber -= 2;
			}
		}
	}
	return;
}