BOJ 6588번 골드바흐의 추측

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/6588/6588/%EC%86%8C%EC%8A%A4.cpp

 

가장 작은 홀수이자 소수인 3부터 N-3 을 해가며 짝을 찾아주면된다.

처음에 시간초과가 뜨길래 문제가 있나 싶었는데

ios::sync_with_stdio(false) 는 사용했으면서 cin.tie(NULL)을 해줘야되는지 몰랐다,, 알았으니 됬다

 

#include <iostream>
using namespace std;
#define Max 1000001
 
bool arr[Max];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 2; i < Max; i++) arr[i] = true;
    for (int i = 2; i * i < Max; i++) {
        if (!arr[i]) continue;
        for (int k = i * i; k < Max; k += i) arr[k] = false;
    }
 
    int num;
    while (1) {
        cin >> num;
        if (!num) break;
        for (int i = 3; i < Max; i+=2) {
            if (arr[i] && arr[num - i]) {
                cout << num << " = " << i << " + " << num - i << '\n';
                break;
            }
        }
    }
 
    return 0;
}