# 백준 : 골드바흐의 추측(6588)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_6588_Goldbach's%20conjecture)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
using namespace std;

#define MAX 1000000

int primarys[MAX + 1];

int main(void)
{
    int input   = 0;
    int check   = 0;
    
    primarys[0] = primarys[1] = 1;
    
    for(int i=2; i*i<=MAX; i++) {
        for(int j=0; (i*(i+j))<=MAX; j++) {
            primarys[(i*i)+(i*j)] = 1;
        }
    }
    while(true) {
        scanf("%d", &input);
        if(input == 0) break;
        else {
            check = 0;
            for(int i=3; i<=(input/2); i++) {
                if((!primarys[i]) && (!primarys[input - i])) {
                    printf("%d = %d + %d\n", input, i, input - i);
                    check = 1;
                    break;
                }
            }
            if(!check) printf("Goldbach's conjecture is wrong.\n");
        }
    }
    return 0;
}

풀이

지난번에 포스팅한 소수 구하기(이곳) 문제에서 나온 '에라토스테네스의 체'를 이용하는 문제이다. 결국 a값이 가장 작을 때의 b값을 도출하면 되므로, 순서대로 검사하던 중에 결과를 만족하는애가 나오면 곧바로 이녀석이 답이라고 알면 된다.
크게 어렵지는 않은 문제였는데, 계속 시간 초과가 나와서 고민을 좀 했다.
문제는 C++에서 사용하는 cin, cout 등의 입출력 함수들이 C에서 사용하던 scanf와 printf 등의 입출력함수보다 실행시간이 매우 높다는 것이다. 그래서 모든 입출력을 C 함수로 바꿔주니 곧바로 정답을 만들어낼 수 있었다.