[백준 1153] 네 개의 소수 [C]

백준 - 1153

---

풀이

"백준 6588, 골드바흐의 추측" 코드를 이용해 풀이했다.

단, 골드바흐의 추측은 짝수인 N에 대해 해당하기 때문에, 입력받은 N이 홀수인 경우 2, 3을, 짝수인 경우 2, 2를 먼저 출력해준 후 출력해준 수 만큼 빼준 N값에 대해 골드바흐의 추측을 사용해 풀이할 수 있다.

단, 8인 경우에는 2, 2, 2, 2이기 때문에 따로 써주거나 더 안정적인 골드바흐의 추측 알고리즘을 사용하면 된다.

---

소스코드

#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#define MAX 1000001
bool Cnum[MAX];
int main(){
    int sq = sqrt(MAX);
    for (int i = 2; i <= sq; i++)
        if (!Cnum[i])
            for (int j = 2*i; j < MAX; j += i)
                Cnum[j] = true;
				
    int N;
    scanf("%d", &N);
    if (N < 8) puts("-1");
    else if (N == 8) puts("2 2 2 2");
    else {
        if (N%2){
            printf("2 3 ");
            N -= 5;
        }else {
            printf("2 2 ");
            N -= 4;
        }
		
        int first = 3, last = N-3;
        while (first <= last){
            if (first+last == N && !Cnum[first] && !Cnum[last]) break;
            first += 2, last -= 2;
        }
        printf("%d %d", first, last);
    }
}

---

출처 및 참고자료

1153번: 네 개의 소수

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