[백준] 17103번: 골드바흐 파티션 (자바 JAVA)

 

 

N은 두 소수의 합이다. 이 N을 골드바흐 파티션이라고 한다. 

골드바흐 파티션의 개수를 구하는 문제이다. 정수 N의 범위가 커서 일반적인 소수 구하는 로직으로 짜면.. 안된다.

소수를 구하는 알고리즘인 에라토스테네스의 체 를 사용해야한다.

 

관련 개념을 읽어보자.

2022.12.17 - [JAVA/알고리즘 공부] - [JAVA] 에라토스테네스의 체 (소수 판별 알고리즘)

 

 

1. 에라토스테네스의 체 알고리즘으로 1~1,000,000 까지 수 중 소수를 판별한다.

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

 

package boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Ex17103 {

	public static void main(String[] args) {

		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			StringBuilder sb = new StringBuilder();
			int cycle = Integer.parseInt(br.readLine());
			int max = 1_000_000;
			boolean chk[] = new boolean[max+1]; // 소수를 체크할 배열
			
			for(int i=0; i<=max; i++) {
				chk[i] = false;
			}
			// 0과 1은 소수가 아님으로 시작
			chk[0] = true; 
			chk[1] = true;
			
			for(int i=2; i*i<=max; i++) {
				for(int j=i*i; j<=max; j+=i) {
					if(chk[j]) { // 이미 소수라고 판별되어있으면
						continue;
					} 
					chk[j] = true;
				}
			}

			while (cycle > 0) {
				cycle--;

				int n = Integer.parseInt(br.readLine());
				
				int cnt = 0;
				
				for (int i = 2; i <= n/2; i++) { 
					if(chk[n-i]==false && chk[i]==false) {
						cnt++;
					}
				}
				
				sb.append(cnt + "\n");
			}

			System.out.println(sb);
		} catch (Exception e) {
			e.printStackTrace();
		}

	}

}