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

백준 - 9020

---

풀이

"백준 6588, 골드바흐의 추측"과 비슷한 문제이다.

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

N = 4인 경우에는 예외로 처리해줬다.

---

소스코드

#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#define MAX 10001
bool cNum[MAX];
int main(){
    int sq = sqrt(MAX-1);
    for (int i = 2; i <= sq; i++)
        for (int j = 2*i; j < MAX; j += i)
            cNum[j] = true;
	
    int T;
    scanf("%d", &T);
    while (T--){
        int N;
        scanf("%d", &N);
		
        if (N == 4){
            puts("2 2");
            continue;
        }
        int first = 3, last = N-3;
        int temp[2] = {first, last};
        while (first <= last){
            if (!cNum[first] && !cNum[last] && first+last == N){
                temp[0] = first;
                temp[1] = last;
            }
            first += 2, last -= 2;
        }
		
        printf("%d %d\n", temp[0], temp[1]);
    }
}

---

출처 및 참고자료

9020번: 골드바흐의 추측

[백준 6588] 골드바흐의 추측 [C]