[Algorithm/Java][백준] 9020 골드바흐의 추측

[BOJ] 9020 골드바흐의 추측

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

문제 접근

짝수 n을 가장 차이가 작은 두 소수의 합으로 나타내는 문제이다. 처음에는 n까지 소수를 구하고 그 수중에서 합을 수할려고 했는데, 코드가 너무 복잡해지고 내가 썼는데도 내가 못알아보는 지경이였다... 그리고 결국은 막혔다
그래서 에라토스테네스의 체를 이용해서 10000까지의 소수를 모두 구했다. 그 다음은 가장 차이가 작은 두 소수의 합을 구하기 위해서 num1은 n/2부터 1씩 감소하고 num2는 n- num1으로 해서 num1,num2 모두 소수인 첫번째 경우가 답이였다.
요약하자면 아래와 같다.
1.에라토스네스의 체로 10000까지 소수를 모두 구한다.
2.1의 결과를 바탕으로 n/2부터 1씩 줄여가면서 num1, num2 모두 소수인 경우를 찾는다.

Code

import java.util.Scanner;

public class BOJ9020 {
    static boolean[] isNotPrime = new boolean[10001];
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        findPrime();
        while(T-- != 0){
            n = sc.nextInt();
            findAnswer(n);
        }
    }
    /**
     * 에라토스테네스의 체를 이용해 10000까지 소수를 구해 isNotPrime에 저장한다.
     * isNotPrime == true -> 소수 아님
     * isNotPrime == false -> 소수
     * */
    public static void findPrime(){
        for(int i = 2; i< isNotPrime.length; i++) {
            if(isNotPrime[i]) continue;
            for (int j = 2 * i; j < isNotPrime.length; j += i) {
                isNotPrime[j] = true;
            }
        }
    }
    /**
     * n/2부터 1씩 감소시키면서 
     * num1,num2 모두 소수인 경우를 찾아서 출력한다.
     */
    public static void findAnswer(int n){
        for(int num1 = n/2; num1 > 0; num1--){
            int num2 = n - num1;
            if(!isNotPrime[num1] && !isNotPrime[num2]){
                System.out.println(num1+" "+num2);
                break;
            }
        }
    }
}

어려웠던 점 / 배운 점 / 느낀 점

boolean을 전역변수로 선언해서 초기화하면 기본값이 false여서 처음에는 boolean isPrime을 선언했다가 boolean isNotPrime으로 바꿨다.
전역변수로 초기화했을 때 기본값은 중요하지 않다고 생각했는데, findPrime이 제대로 작동하지 않아서 문제를 찾는데 좀 걸렸다.(에라토스테네스가 잘못된 줄 알았다....)