[BaekJoon/백준] 6588번 - 골드바흐의 추측

#include <iostream>

int N;
bool check[1000001]; // '100만' 수 까지

using namespace std;

int main() {
    
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    
    for(int i = 2; i * i <= 1000000; i++) {
        
        if(check[i]) continue; // 이미 약수의 배수로 체크되었을거임.
        
        for(int j = i + i; j <= 1000000; j+=i)
            check[j] = true;
        }

    
    while(1) {
        cin >> N;
        
        if(N == 0)
            break;
                
        // i * i <= N 아닌 것 주의. 8 = 3 + 5 임. 덧셈인만큼 절반까지만 보면 되겠으니 N / 2로 설정.
        for(int i = 2; i <= N/2 ; i++) {
            if(!check[i] && !check[N - i]) {
                
                cout << N << " = " << i << " + " << N - i << "\n";
                
                break;
            }
            
            if(i == N/2) // 끝까지 못찾은 경우
                cout << "Goldbach's conjecture is wrong.\n";
        }
    }
}

에라토스테네스의 체를 이용해서 빠르게 소수를 구한 뒤,

 

이 소수들을 앞에서부터 찾아보면서 덧셈으로 해당 숫자를 형성할 수 있는지 알아보면 된다.

 

에라토스테네스의 체를 이용해 소수를 구할 때는 반복문을 N의 루트까지만 돌면 되는 성질이 있으며,

 

문제에서 해당 수를 덧셈으로 형성하면 되기에, N의 절반까지만 수만 보면 이에 대응하는 수를 찾기에 충분하다.

(대칭 구조를 갖기 때문)

 

 

시간초과를 겪는 분들은, 아래 링크를 참고하면 좋을 것 같다.

https://www.acmicpc.net/board/view/69452

글 읽기 - 시간초과..ㅠㅠ