[BOJ] 6588. 골드바흐의 추측

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

6588번: 골드바흐의 추측

문제에서 n의 범위는 (6 ≤ n ≤ 1000000)이다.

골드바흐의 추측은 10의 18 제곱까지는 증명되었다고 하므로

두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에 "Goldbach's conjecture is wrong."을 출력하라고 문제에 나와있지만

안 해줘도 될 것 같다.

 

소수는 에라토스테네스의 체를 이용해서 n의 범위만큼 미리 구해서 배열에 저장한다.

n이 두 소수 p와 q로 이루어져 있다고 했을 때,

p + q = n

n - p = q

이므로 n에서 소수를 뺀 값이 소수이면 답을 바로 출력한다.

 

참고로 c++에서

ios_base::sync_with_stdio(false);

cin.tie(nullptr);

를 써주면 입출력 속도를 높일 수 있다고 한다.

대신에 printf, scnaf 등은 사용하면 안 된다.

 

#include <iostream>
using namespace std;
const int MAX = 1000000;
int prime[MAX];
int cnt;
bool check[MAX+1];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //소수를 구해준다.
    for(int i=2; i*i<=MAX; i++) {
    	//이미 소수가 아닌걸로 체크되어 있는 경우
        if(check[i] == true) continue;

		//위의 조건에 걸리지 않았다면 소수이므로 소수 배열에 추가
        prime[cnt++] = i;
        
        //현재 소수의 배수들은 소수가 아니므로 체크해준다.
        for(int j=i+i; j<=MAX; j+=i) {
            check[j] = true;
        }

    }

    while(true) {
        int n;
        cin >> n;
        if(n == 0) break;
        for(int i=1; i<cnt; i++) {
            if(check[n-prime[i]] == false) {
                cout << n << " = " << prime[i] << " + " << n-prime[i] <<  "\n";
                break;

            }
        }
    }

    return 0;
}