[JAVA] 백준 (실버2) 17103번 골드바흐 파티션

링크

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

---

문제 설명

(정답률 36.602%)

• 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

---

입력 예제

5
6
8
10
12
100

---

출력 예제

1
1
2
1
6

---

정답 코드

import java.io.*;

public class Main {
    final static int Max = 1000000;
    static boolean[] primeNumber = new boolean[Max + 1];

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        findPrimeNumber(primeNumber);
        int T = Integer.parseInt(br.readLine());
		//테스트 케이스만큼 반복
        for (int i = 0; i < T; i++) {
            int num = Integer.parseInt(br.readLine());
            int cnt = 0;

			//덧셈이 동일할 경우는 (2+3 = 3+2)같은 케이스로 판단하기 때문에
            //for문은 num/2만큼 반복
            for (int j = 2; j <= num / 2; j++) {
            	//j와 num-j이가 둘다 소수일 경우 카운트
                if (primeNumber[j] && primeNumber[num - j]) {
                    cnt++;
                }
            }

            System.out.println(cnt);
        }

    }
    //배열의 소수 여부 판단 메소드    
    static void findPrimeNumber(boolean[] arr) {
		//일단 모든 인덱스를 true로 할당
        for (int i = 0; i <= Max; i++) {
            arr[i] = true;
        }
        arr[0] = arr[1] = false;	//0과 1은 소수가 아니다

		//에라토스테네스의 체를 이용
        //소수가 아닌 인덱스는 false로 할당
        for (int i = 2; i * i <= Max; i++) {
            if (arr[i]) {
                for (int j = i * i; j <= Max; j += i) {
                    arr[j] = false;
                }
            }
        }
        
    }

}

---

정리

일전에 골드바흐의 추측문제를 풀어봤기 때문에 쉽게 풀 수 있었다.
하지만 에라토스테네스의 체는 익숙치 않아서 얄고리즘이 바로 생각이 나지 않았다.