9020 골드바흐의 추측

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

---

8=3+5, 20=17+3 ... 이렇게 소수+소수=짝수를 할 수 있다는게 골드바흐의 추측이다.

 

반대로 생각하면 짝수에서 어느 소수를 빼면 소수가 나오는 경우가 있다는 말이다.

 

테스트 케이스에 대해서 소수 판별을 해야하므로 소수 리스트를 미리 구해두는게 더 좋겠다.

 

bool isPrime[10001];
void find(){
    for(int i=2; i<=10000; i++){
        isPrime[i] = true;
        for(int j=2; j*j<=i; j++){
            if(i%j == 0){
                isPrime[i] = false;
                break;
            }
        }
    }
}

미리 참으로 설정하고 나누어 떨어지는 경우 거짓으로 만든 후 반복을 끝낸다.

 

#include <iostream>
bool isPrime[10001];
void find(){
    for(int i=2; i<=10000; i++){
        isPrime[i] = true;
        for(int j=2; j*j<=i; j++){
            if(i%j == 0){
                isPrime[i] = false;
                break;
            }
        }
    }
}
int main(){
    find();
    int T, N;
    scanf("%d", &T);
    for(int i=0; i<T; i++){
        scanf("%d", &N);
        for(int j=N/2; j<=N; j++){
            if(isPrime[j] && isPrime[N-j]){
                printf("%d %d\n", N-j, j);
                break;
            }
        }
    }
}

매 입력이 들어올 때마다 짝수 = 소수 + 소수 판별을 해본다.

 

N/2부터 시작한다는 점은 최대한 j, N-j의 차이를 줄이기 위해서이다.