[Java] 소수 판정 (골드바흐의 추측)

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

6588번: 골드바흐의 추측

 

오늘 푼 문제는 코딩테스트 단골 출제 문제인 소수 판정 골드바흐의 추측이다. 1년 전에 파이썬으로 풀었던 문제인데 이번에 재채점 결과 시간초과로 틀렸다고 알림이 와서 자바로 다시 풀어봤다.

소수 판정 문제는 시간초과를 넘지 않는 게 관건인 문제라서 에라토스테네스의 체를 활용하여 Time Complexity를 획기적으로 줄여야만 하는데, 이 문제는 에라토스테네스의 체를 포함해 소수 판별 테이블을 생성해 함수를 여러 번 돌리지 않도록 하는 것이 중요하다.

 

 

진짜 어처구니 없는 실수를 했었는데 문제 조건이 6 <= n < 1000000라서 1000000개의 배열을 생성해야 하는데 0을 하나 뺀 100000개의 배열을 생성해 버려서 삽질했다 (0 개수 세기 이슈). 어쩐지 인덱스 오류가 날 부분이 없는데 계속 오류라서 알아내는데 고생 좀 했다. 

 

 

이전 구간 합 구하기 문제에서 배운 것처럼 StringBuilder에 문자열을 더해놓고 마지막에 출력해 시간 단축.

 

 

public class Main {

    static boolean prime[] = new boolean[1000001];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int number;
        boolean check = false;
        prime[0] = prime[1] = false;
        prime[2] = true;

        for (int i = 3; i <1000001; i++) {

            if(primeNumber(i)) prime[i] = true;
            else prime[i] = false;
        }


        while (true) {
            number = Integer.parseInt(br.readLine());
            if (number == 0) break;

            for (int i = 2; i < (number/2 +1); i++) { //1은 소수가 아니므로 2부터 시작

                if (prime[i] && prime[number-i]) {
                    {sb.append(number + " = " + i + " + " + (number - i) + "\n"); check=true; break;}
                }
            }
            if(check==false) sb.append("Goldbach's conjecture is wrong." + "\n");
            check=false;

        }

        System.out.println(sb);
    }

    public static boolean primeNumber(int N){

        for(int i=2; i<(Math.sqrt(N)+1); i++){
            if(N % i ==0) return false;
        }
        return true;
    }

}