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

#문제

www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

#풀이 & 학습한 내용

ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); 이 없으면 시간초과가 나는 문제이다. 그리고 문제를 풀 때는 supremo7.tistory.com/116에서 이용한 에라토스테네스의 체를 통해 해결한다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
bool prime[1000002];//지워졌으면 true(1), 소수인게 false(0)
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    prime[1] = true;
    for (int i = 2; i*i <= 1000000; i++) {
        if (prime[i] == false) {
            for (int j = i * 2; j <= 1000000; j+=i) {
                prime[j] = true;
            }
        }
    }
 
    int num;
    while (1) {
        cin >> num;
        if (num == 0)
            break;
        for (int i = 3; i <= num / 2; i += 2) {
            if (prime[i] == false && prime[num - i] == false) {
                cout << num << " = " << i << " + " << num - i << '\n';
                break;
            }
        }
    }
 
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Math/BOJ_6588.cpp

HoYoungChun/BOJ_algorithm