[BOJ/백준] 17103 - 골드바흐 파티션

17103번: 골드바흐 파티션

---

에라토스테네스의 체

---

---

• 제목

 

---

• 조건

시간 제한 : 0.5 초

메모리 제한 : 512 MB 

---

• 문제

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

 

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

---

• 입력

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

---

• 출력

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

---

예제 입력1	예제 출력1
5 6 8 10 12 100	1 1 2 1 6

---

import java.util.*;
public class Main {
    public static boolean isPrime(int num){
        if(num == 1) return false;
        for(int i = 2; i * i <= num; i++){
            if(num % i == 0){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        HashSet<Integer> set = new HashSet<Integer>();
        int N = scanner.nextInt();

        for(int i = 2; i < 1000000; i++){
            if(isPrime(i)) set.add(i);
        }
        ArrayList<Integer> arr = new ArrayList<Integer>(set);
        Collections.sort(arr);
        for(int i = 0; i < N; i++){
            int num = scanner.nextInt();
            int cnt = 0;
            for(int j = 0; arr.get(j) < num ; j++){
                if(num - arr.get(j) < arr.get(j)) break;
                if(set.contains(num - arr.get(j))) {
                    cnt += 1;
                }
            }
            System.out.println(cnt);
        }
        scanner.close();
    }
}