📌 문제

[17103] 골드바흐 파티션

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

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

⬇️ 입력

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

⬆️ 출력

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

💡 코드

✅ 에라토스테네스의 체 알고리즘을 사용한 getPrime() 메서드에서 10,000,000까지의 수 중 소수와 합성수를 구분한다. 이후 입력받은 n에 대하여 골드바흐 파티션을 구해주면 되는데, 더하는 두 수가 모두 소수여야 하므로, 두 수의 인덱스에 해당하는 요소의 값이 false이면서 두 수의 합이 n을 만족할 때 cnt를 증가시킨다.

두 수의 순서가 바뀐 경우는 같은 파티션으로 취급하므로, n/2번만 실행해주면 되고, 각 수가 배열의 인덱스와 대응하므로 두 수는 각각 j, n-j로 나타낼 수 있다.

import java.io.*;
public class Main {
	
	static boolean[] prime = new boolean[10000001];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		getPrime();
		int t = Integer.parseInt(br.readLine());
		
		for(int i=0;i<t;i++) {
			int n = Integer.parseInt(br.readLine());
			int cnt = 0;
			
			for(int j=2;j<=n/2;j++) {
				if(!prime[j] && !prime[n-j]) cnt++;
			}
			sb.append(cnt).append("\n");
		}
		bw.write(sb + "");
		
		br.close();
		bw.close();
	}
	
	static void getPrime() {
		prime[0] = prime[1] = true;
		
		for(int i=2;i<=Math.sqrt(prime.length);i++) {
			if(prime[i]) continue;
			for(int j=i*i;j<prime.length;j+=i) {
				prime[j] = true;
			}
		}
	}
}