6588번: 골드바흐의 추측

시간초과를 해결하는게 관건인 문제다.

우선은 에라토스테네스의 체를 이용해 홀수 소수를 구한다.

이후 가장 큰 b - a를 구하기위해 범위내의 가장 작은 홀수 소수(front)와 가장 큰 홀수 소수(end)부터 시작하여

더한 값이 주어진 값보다 크다면 end를 한칸 줄이고

주어진 값보다 작다면 front를 한칸 늘린다.

이런식으로 front값이 end값보다 작을 때까지 반복하면 답이 구해진다.

단! 1000000이라는 넓은 범위로 인해 탐색하는데 상당히 소요되므로

lower_bound를 통해 주어진 값보다 큰 인덱스를 구해서 end값에 넣어준다.

#include <iostream>
#include <vector>
#include <algorithm>
 
int check[1000001] = { 0 };
 
int main(void) {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    
    std::vector<int> decimal;
    for (int i = 2; i < 1000001; i++) {
        if (check[i]) continue;
        int count = 1;
        while (i * count < 1000001) {
            check[i * count] = 1;
            count++;
        }
        if (!(i % 2)) { continue; }
        decimal.push_back(i);
    }
 
    int val;
    int front = 0, end = decimal.size() - 1;
    while (true) {
        front = 0, end = decimal.size() - 1;
        std::cin >> val;
        if (val == 0) {
            break;
        }
        std::vector<int>::iterator low;
        low = std::lower_bound(decimal.begin(), decimal.end(), val);
        end = low - decimal.begin();
        while (true) {
            if (decimal[front] + decimal[end] == val) {
                std::cout << val << " = " << decimal[front] << " + " << decimal[end] << "\n";
                break;
            }
            else if (decimal[front] + decimal[end] > val) {
                end--;
            }
            else if (decimal[front] + decimal[end] < val) {
                front++;
            }
            if (front > end) {
                std::cout << "Goldbach's conjecture is wrong." << "\n";
                break;
            }
        }
    }
 
    return 0;
}