[BOJ] 백준 9020 골드바흐의 추측

Approach

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

 

2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다고 한다.

이러한 수를 "골드바흐 수"라고 한다.

 

해당 짝수를 [두 소수의 합]으로 표현할 때

그 조합을 "골드바흐 파티션" 이라고 한다고 한다.

 

Test Case가 주어지고 숫자 N이 주어질 때,

두 소수의 차이가 가장 작은 골드바흐 파티션을 구해야 한다.

 

문제 조건상 N의 최대값은 10,000이므로

1~10,000까지의 소수를 미리 구해놓는다.

(코드에서는 숫자 0, 1, 2에 대해서는 미리 소수 처리.

 

[에라토스테네스의 체] 개념을 이용한다.

소수 (Prime Number) 찾기 - 3

 

두 수의 차이가 적으려면 절반의 수치부터 탐색하면 된다.

ex) 16 → 8 + 8, 14 → 7 + 7

두 수가 소수여야 하기 때문에 소수 여부를 판단한다.

예를 들어 16의 절반 8(= pivot)부터 탐색한다.

8 → 7 → 6 → 5 ... → 1

 

나머지 한개의 숫자는 N - pivot 에 대응된다.

8 → 9 →  → 5 ... → 15

 

---

#include <stdio.h>
const int MAX_N = 1e4;
int TC, N;
int pArr[MAX_N + 2] = { 0, 1, 0, }; // 숫자 0, 1, 2에 대한 소수 처리

int main() 
{
	// freopen("input.txt", "r", stdin);		

	// 소수 구하기
	for (int p = 2; p <= MAX_N; p++) 
	{
		if (!pArr[p]) 
		{
			// 해당 배수에 대한 소수 여부 처리
			for (int i=2; p * i <= MAX_N; ++i)
			{
				pArr[p*i] = 1;
			}
		}
	}

	scanf("%d", &TC);
	while (TC--) 
	{
		scanf("%d", &N);
		for (int i = N/2; i > 0; i--)
		{
			// 두 숫자가 소수인 경우
			if (!pArr[i]&& !pArr[N - i]) {
				printf("%d %d\n", i, N - i);
				break;
			}
		}
	}
}