[C 언어] 백준 9020. 골드바흐의 추측

---

9020. 골드바흐의 추측 (누르면 해당 문제로 이동)

소수 응용 문제 2

 

제약사항)

시간 : 2 초

메모리 : 256 MB

 

문제)

1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다.

예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6=2x3 이기 때문에 소수가 아니다.

 

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다.

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

또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다.

예를 들면, 4=2+2, 6=3+3, 8=3+5, 10=5+5, 12=5+7, 14=3+11, 14=7+7이다.

10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

 

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오.

만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

 

입력)

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다. (4<=n<=10,000)

 

출력)

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다.

출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

 

입출력 예제

입력	출력
3 8 10 16	3 5 5 5 5 11

 

---

 

풀이 순서)

1. num 배열에 소수인지 아닌지를 판별하여 값을 저장합니다. (0이면 소수, 1이면 소수가 아닌 경우 입니다.)

2. n 을 입력받아 반복문을 이용해 두 소수의 합으로 n을 구할 수 있는지 확인합니다.

    : 두 수의 합이기 때문에 반복문에서 n/2 ~ 0 까지만 확인했습니다.

 

---

 

소스코드 및 결과 (C)

#include <stdio.h>
#include <math.h>

#define size 10000

int num[size] = { 0, };

int main() {
	int T, i, j;
	int n, tmp;

	for (i = 2; i <= (int)sqrt(size); i++)
		for (j = i * i; j <= size; j += i)
			if (num[j] % i == 0)
				num[j] = 1;

	scanf("%d", &T);

	for (i = 0; i < T; i++) {
		scanf("%d", &n);

		for (j = n / 2; j > 0; j--) {
			if (num[j] != 1 && num[n - j] != 1) {
				printf("%d %d\n", j, n - j);
				break;
			}
		}
	}

    return 0;
}

 

메모리 : 1152 KB

시간 : 4 ms

코드길이 : 453 B

 

 

---