백준 6588번 - 골드바흐 추측 (C++)

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

 

에라토스테네스의 체를 이용해 소수르 판별하고, 이후 완전탐색을 진행했는데 시간초과가 났다.

 

그래서 두번돌면 안되는 것을 확인했고,  i, n - i 가 둘 다 소수인 것을 찾아야한 다는 것을 생각해내었다.

 

#include <iostream>
#include <vector>

#define MAX 1000000
using namespace std;

vector<int> primeNum;
bool* check = new bool[MAX];

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(0);
    for(int i = 0; i <= MAX; i++) check[i] = false;
    for(int i = 2; i * i <= MAX; i++){
        if(check[i] == false){
            for(int j = i * i; j <= MAX; j += i){
                check[j] = true;
            }
        }
    }

    int tmp = -1;
    cin >> tmp;
    
    while(tmp != 0){
        bool flag = false;
        for(int i = 3; i <= MAX; i++){
            if(check[i] == false && check[tmp - i] == false) {
                cout << tmp << " = " << i << " + " << tmp - i << '\n';
                flag = true;
                break;
            }
        }
        if(!flag){
            cout << "Goldbach's conjecture is wrong.\n";
        }
        cin >> tmp;
    }
}