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

6588번: 골드바흐의 추측

에라토스테네스의 체를 이용한 문제이다. 에라토스테네스의 체를 먼저 이용해 최댓값까지의 소수를 모두 구해주고 시작하였다. 반복문을 돌면서 현재 소수일 경우 n - i 또한 소수인지 확인한 후 소수이면 이를 출력해주었다. 문제자체는 어렵지 않았지만 시간 초과가 계속 났었다. 해결법은 endl 대신 \n을 사용하는 것이었다. endl이 느리다는 것은 알고 있었지만 이정도로 차이가 날 줄은 몰랐다.... 주의하자.

#include <iostream>

#define SIZE 1000001

using namespace std;

int n;
bool p[SIZE];

void prime() {
    for (int i = 2; i * i <= SIZE; i++) {
        if (p[i]) continue;

        for (int j = i + i; j <= SIZE; j += i) {
            p[j] = true;
        }
    }
}

void solution() {
    int pp = 0;

    for (int i = 2; i <= n; i++) {
        if (p[i]) continue;

        if (!p[n - i]) {
            pp = i;
            break;
        }
    }

    if (pp == 0) {
        cout << "Goldbach's conjecture is wrong.\n";
    }
    else {
        cout << n << " = " << pp << " + " << n - pp << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    prime();

    while (1) {
        cin >> n;

        if (n == 0) break;

        solution();
    }

    return 0;
}