[백준] 17103번 - 골드바흐 파티션(두 소수의 합)

>>문제 바로가기<<

2보다 큰 짝수 N을 두 소수의 합으로 나타내는 파티션이 몇개나 존재하는지 물어보는 문제이다.

입력받는 N마다 하나하나 소수 집합을 구한 후,
둘이 합해서 N이 나오는지를 일일히 확인해야 하나?

그러면 실행시간이 굉장히 커질것이다.

때문에 공통적으로 사용할 수 있는 소수 집합을 미리 만들어 놓는것이 간편할 수 있다.

---

boolean[] isPrime = new boolean[1000000];
Arrays.fill(isPrime, true);		// 모든 값을 true로 fill.
isPrime[0] = false;				// 0은 소수x
isPrime[1] = false;				// 1은 소수x
for(int i=2; i * i<=1000000; i++){
	if(isPrime[i]){
    	for(int j=i * i; j<=1000000; j+=i){
        	isPrime[j] = false;
        }
    }
}   	

위는 에라토스테네스의 체(Sieve)라고 불리는 알고리즘이다.
어떤 수 N 이하의 소수를 모두 찾을 때,
“소수가 아닌 수를 걸러내는 방식”이다.

@ 작동 원리

1. 2는 소수다. (i에서 판단)
   => 2를 남기고 2의 배수는 모두 거름 (j에서 거름)
2. 다음 수 3은 소수다.
   => 3을 남기고 3의 배수는 모두 거름
3. 다음 수 4는 이미 걸러졌으므로 넘어간다.
4. 다음 수 5는 소수다.
   => 5를 남기고 5의 배수는 모두 거름
   ...

이렇게 √n까지 반복(i * i <= n)하면,
남은 수는 모두 소수가 된다.

배열의 크기가 1,000,000라서 시간이 굉장히 오래걸릴것 같아 보이지만 생각보다 느리지 않다.

---

두 소수의 합이 N이 되는지를 보고싶으면, 소수 p와 N-p가 isPrime 집합에 속하는지를 확인하면 된다.

위 정보를 바탕으로 설계한 코드는 다음과 같다.

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

class Main{
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        boolean[] isPrime = new boolean[1000000];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for(int i=2; i*i<1000000; i++){
        	if(isPrime[i]){
            	for(int j=i*i; j<1000000; j+=i){
                	isPrime[j] = false;
                }
            }
        }
        
        int T = Integer.parseInt(br.readLine());
        for(int i=0; i<T; i++){
        	int N = Integer.parseInt(br.readLine());
            int count = 0;
            for(int j=2; j<=N/2; j++){	// N/2까지만 반복: p와 N-p의 중복 방지
            	if(isPrime[j] && isPrime[N-j]){
                	count++;
                }
            }
            bw.write(count + "\n");
        }
    bw.flush();
    bw.close();
    }
}

맞았습니다!!