[C]백준 09.기본수학2: 9020

백준 9020

내코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

void sieve(int arr[], int count) {
	for (int i = 2; i < count; i++) {
		arr[i] = i;
	}
	for (int i = 2; i < count; i++) {
		if (arr[i] == 0)
			continue;
		for (int j = 2 * i; j < count; j += i) {
			arr[j] = 0;
		}
	}
}

int main()
{
	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; i++) {
		int n;
		int arr[10001] = { 0, };
		sieve(arr, sizeof(arr) / sizeof(int));


		scanf("%d", &n);
		int a = n / 2;
		int b = n / 2;
		while (arr[a] == 0 || arr[b] == 0) {
			a--;
			b++;
		}
		printf("%d %d\n", a, b);
	}
	return 0;
}

골드바흐 파티션은 짝수를 두 소수의 합으로 표현하고, 그 경우가 여러가지인 경우엔 두 소수의 차이가 가장 작은 것으로 결정하는 것이다. 특정 수 n의 골드바흐 파티션을 만족하는 두 소수를 a, b라고 생각했을 때 두 소수의 차이를 적게 하기 위해 a와 b에 n/2값을 넣은 후 a와 b가 소수인지 확인하고 아니라면 a는 1감소, b는 1증가하는 것을 반복하는 방식으로 문제를 풀고자 했다.

a와 b가 소수인지 확인하기 위해 먼저 에라토스테네스의 체를 이용하고자 했다. 그래서 에라토스테네스의 체처럼 이용할 arr배열을 만들었다. sieve는 arr배열과 그 크기를 넘겨주면 그 크기까지의 에라토스테네스의 체를 만들어주는 함수이다. 따라서 sieve함수에 arr배열과 그 크기를 넘겨주면 arr배열의 인덱스 중 소수가 아닌 값은 배열값으로 0을 가지게 된다. i가 소수라면 arr[i]의 값은 i이지만 i가 소수가 아니라면 arr[i]의 값은 0이다. 따라서 반복문의 조건을 arr[a]==0||arr[b]==0 즉, a와 b가 소수가 아닐때로 설정하여 반복해주었다.