[C언어] 9020번 골드바흐의 추측

소수를 미리 구해서 배열을 만든 뒤

가장 두 소수의 차가 적은 짝수 n을 만드는 소수 두 개의 조합을 찾아야 한다.

 

n/2에서 i를 더하거나 뺀 값이다.ns 배열에서 소수일 경우 0, 소수가 아닌 경우 1로 이미 배열을 완성했기 때문에ns[i] || ns[n-i] 두 수 모두가 소수로 0일 때 (False) 반복문을 빠져나오면 소수 i와 n-i를 쉽게 찾을 수 있다.

4	6	8	10	12	14	16	18	20	22
2	3	3	5	5	7	5	7	7	11
n/2	n/2	n/2-1	n/2	n/2-1	n/2	n/2-3	n/2-2	n/2-3	n/2
2	3	5	5	7	7	11	11	13	11
n/2	n/2	n/2+1	n/2	n/2+1	n/2	n/2+3	n/2+2	n/2+3	n/2

 

#include <stdio.h>
#define MAX 5100

int main()
{
	int T, n, i, j;
	char ns[MAX+1] = {1,1};

	for (i = 2; i * i < MAX + 1; i++)
		if (!ns[i])
			for (j = i * i; j < MAX + 1; j += i)
				ns[j] = 1;
	
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d", &n);
		for (i = n / 2; ns[i] || ns[n-i]; i++);
		printf("%d %d\n", n - i, i);
	}

	return 0;
}