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

백준 - 6588

---

풀이

에라토스테네스의 채로 소수가 아닌 수들을 먼저 구한 후 풀이를 했다.

두 수의 합이 N과 같고, 두 수가 소수인경우에만 반복문을 종료해 답을 출력해주면 된다.

---

소스코드

#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#define MAX 1000001
int main(){
    int sq = sqrt(MAX-1);
    bool not_prime[MAX] = {0,};
    for (int i = 2; i <= sq; i++)
        for (int j = 2*i; j < MAX-1; j += i)
            not_prime[j] = true;
	
    while (1){
        int N;
        scanf("%d", &N);
        if (!N) break;
		
        int first = 3, last = N-3;
		
        while (first <= last){
            if (first+last == N && !not_prime[first] && !not_prime[last]) break;
            first += 2, last -= 2;
        }
		
        if (first > last) puts("Goldbach's conjecture is wrong.");
        else printf("%d = %d + %d\n", N, first, last);
    }
}

---

출처

6588번: 골드바흐의 추측