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

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

6588번: 골드바흐의 추측

---

Solved By: Sieve of Eratosthenes

 

Sieve of Eratosthenes를 사용하되 체크하는 부분을 sqrt(MAX)까지만 해도 되는 것을 알고서 구현을 해줍니다.

그리고, 방문 배열을 사용하지 않는 코드를 짜서 문제를 풀어봅니다.

왜냐하면 Sieve of Eratosthenes에서 사용했던 num 배열을 다시 한 번 사용하여 n에서 어떤 소수를 뺀 값이 소수인지 판별할 수 있기 때문입니다.

#include <iostream>
#include <vector>
#include <cmath>
#define MAX 1000001
using namespace std;

vector<int> prime;
int num[MAX];

void getPrime(){
    for(int i = 2; i < MAX; i++) num[i] = i;
    for(int i = 2; i < sqrt(MAX); i++){
        if(num[i] != 0){
            for(int j = i + i; j < MAX; j += i){
                num[j] = 0;
            }    
        }
    }
    
    for(int i = 3; i < MAX; i++){
        if(num[i]) prime.push_back(i);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    getPrime();
    while(true){
        cin >> n;
        if(n == 0) break;
        
        bool flag = false;
        for(auto v : prime){
            if(num[n - v] != 0){
                flag = 1;
                cout << n << " = " << v << " + " << n - v << '\n';
                break;
            }
        }
        
        if(!flag) cout << "Goldbach's conjecture is wrong." << '\n';
    }
    return 0;
}