BOJ 6588 [골드바흐의 추측]

BOJ 골드바흐의 추측 : www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

오랜만에 푸는 앨거리즘,,,

골드바흐 추측에 관련한 소설을 중학교때 읽었는데, 하나도 기억이 안난다. 어쨌든

 

진짜 뻘짓을 많이했던 문제다.

처음에 계속 시간초과가 떠서 대체 뭐시 문제인가...하고 봤더니

cin.tie(NULL)

ios::sync_with_stdio(0)를 추가해야 한다고 한다...

그래서 추가하고 다시 제출하니 또 시간초과가 뜬다.

 

더 알아보니 개행도 endl이 아니라 "\n"으로 하란다...

 

그래서 또 썼더니, 이젠 틀렸다고 나온다.

 

개고생한 결과... 출력을

"C = A + B" 가 아니라 그냥 "A + B"만 출력하고 있었던 것이다.

 

출력 형식대로 해주니 맞았습니다가 떴다. 어찌나 기쁘던지,,,

 

 

소수를 에라토스테네스 체로 체크해두면 다 끝난 문제이다.

 

#include <iostream>
#include <utility>
#include <cmath>
#define MAX_SIZE 1000000
 
using namespace std;
 
bool primeList[1000001];
 
int N, a, b;
void SetPrimeList() 
{
    primeList[1] = true;
    for (size_t i = 2; i <= sqrt(MAX_SIZE); i++)
    {
        for(size_t j = i*2; j <= MAX_SIZE; j+=i) 
        {
            if(primeList[j]) continue;
            primeList[j] = true;
        }   
    }
}
 
pair<int, int> GetResult(int n) 
{
    int first = 0;
    int second = 0;
    
    for (int i = n; i > 0; i--)
    {
        if(!primeList[i] && !primeList[n-i] && (i % 2) != 0 && ((n-i) % 2 ) != 0) 
        {
            first = n-i;
            second = i;
            break;
        }
    }
 
    return make_pair(first, second);
}
 
int main() 
{
    SetPrimeList();
 
    cin.tie(NULL);
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    
    while(true) 
    {
        cin >> N;
        if(N == 0) 
        {
            break;
        }
 
        pair<int, int> result = GetResult(N);
 
        if(result.first == 0) 
        {
            cout << "Goldbach's conjecture is wrong.\n";
        }
        else 
        {
            cout << N << " = " << result.first << " + " << result.second << "\n";
        }
    }
    return 0;
}