백준 9020번 C언어 풀이

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

골드바흐의 추측을 구현하는 문제.

 

언제나 그렇듯 에라토스테네스의 체를 범위에 맞게 만든 후에, 조건에 맞는 골드바흐 파티션을 찾으면 된다.

 

파티션이 여러개 존재하는 경우 그 차이가 제일 적은 파티션을 출력해야 하는데, 이를 어떻게 처리할까 하다가, 처음부터 주어진 수의 절반값에서 시작하여 그 차이를 벌려가다가 파티션이 발견되면 끝내는 방식으로 접근하면 됐다.

 

#include <stdio.h>

int main () {
    int seive[10001] = {0, 0};
    for (int i = 2; i < 10001; i++) {
        seive[i] = 1; 
    }
    for (int i = 2; i < 10001; i++) {
        if (seive[i]) { 
            for (int p = 2; i*p < 10001; p++) {
                seive[i*p] = 0;
            }
        }
    }
    int T, n, gold_part;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        gold_part = n >> 1; // 절반값
        while (gold_part) {
            if (seive[gold_part] && seive[n - gold_part]) // 골드바흐 파티션이 발견됨
                break;
            else
                gold_part--;
        }
        printf("%d %d\n", gold_part, n - gold_part);
    }
    return 0;
}