백준 17103 - 골드바흐 파티션

Java

17103 번 - 골드바흐 파티션

문제

• 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.
  짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.
  (2 < N ≤ 1,000,000)

접근 방법

에라토스테네스의 체를 이용하여 문제를 해결하였다.
각 소수를 인덱스로 하는 배열로 소수들을 나타낸다.
모든 소수를 구했다면, 2부터 n / 2까지 탐색한다.
i와 n-i의 합은 n이므로, i와 n-1 둘다 소수이면 골드바흐 파티션에 성립하므로 결과 값을 증가시킨다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, MAX = 1000000;
	static long result;
	static boolean[] prime;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int tc = stoi(br.readLine());
    	
    	prime = new boolean[MAX + 1];
    	Arrays.fill(prime, true); 	// true는 소수인 것으로 간주
    	int num = 0;
    	// ----------에라토스테네스의 체 시작----------
    	for(int i = 2; i <= MAX; i++) {
    		num = i;
    		if(!prime[i])		// 소수가 아니면 넘긴다
    			continue;
    		num += i;
    		while(num <= MAX) {	// 현재 소수의 배수 값들을 전부 소수가 아니다
    			prime[num] = false;
    			num += i;
    		}
    	}
    	prime[0] = false;
    	prime[1] = false;
    	// ----------에라토스테네스의 체 끝----------

    	for(int idx = 0; idx < tc; idx++) {
    		n = stoi(br.readLine());
    		result = 0;
    		
    		for(int i = 2; i <= n / 2; i++) {
    			// 현재 값과, n - 1값 모두 소수이면 결과 증가
    			if(prime[i]) {
	    			if(prime[n - i])
	    				result++;
    			}
    		}
    		System.out.println(result);
    	}
    	
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점

없습니다.