[백준알고리즘] 9020번: 골드바흐의 추측 -C++

[백준알고리즘] 9020번: 골드바흐의 추측 -C++

9020번: 골드바흐의 추측 (acmicpc.net)

9020번: 골드바흐의 추측

다른 소수 문제와 마찬가지로 에라토스테네스의 체를 사용해서 범위 내의 모든 수에 대한 소수 판정을 먼저 실시했다.

 

이후 \(n\)이 입력되면 \((n/2, n-n/2)\) 쌍이 모두 소수인지 확인을 한다. 

 

두 수가 모두 소수라면 해당 쌍은 골드바흐 파티션이 된다.

 

또한 문제의 조건에서 소수 합이 여러 개가 존재한다면 그 차이가 가장 작은 값을 출력하라고 했기 때문에, 이 또한 \(n/2\)부터 \(1\)까지 한 수를 감소시키면서 찾기 때문에 만족하게 된다.

 

로직 자체는 쉽다.

 

에라토스테네스 체 채고!

 

#include <iostream>

#define NUM_SIZE 10000
#define TOTAL_SIZE NUM_SIZE + 1

bool field[TOTAL_SIZE];

void eratosthenes(void);
void solve(void);

int main(void)
{
	eratosthenes();
	solve();
	return 0;
}

void eratosthenes(void)
{
	std::fill_n(field, TOTAL_SIZE, true);

	field[0] = field[1] = false;
	for (int i = 2; i < int(TOTAL_SIZE / 2); i++)
	{
		if (!field[i]) continue;

		int temp = 2;
		while (i * temp < TOTAL_SIZE)
		{
			field[i * temp] = false;
			temp++;
		}
	}
}

void find_partition(int n)
{
	int s = int(n / 2);
	for (int i = s; i > 1; i--)
	{
		if (!(field[i] && field[n - i])) continue;
		std::cout << i << " " << n - i << std::endl;
		break;
	}
}

void solve(void)
{
	int test_case;
	std::cin >> test_case;

	for (int t = 0; t < test_case; t++)
	{
		int n;
		std::cin >> n;

		find_partition(n);
	}
}

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다