[JAVA] 백준 17103 골드바흐 파티션

17103번: 골드바흐 파티션 (acmicpc.net)

17103번: 골드바흐 파티션

 

 

풀이 과정 

 

골드바흐의 추측

- 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다 

 

골드바흐 파티션 

- 짝수 N을 두 소수의 합으로 나타내는 표현 

 

 

- 각 테스트 마다 모든 소수 배열을 생성할 필요 없음

- 입력 조건 중 가장 큰 숫자(10000000) 의 소수 조합을 생성 한 후 이용 

- n/2번씩 반복문을 돌면서 해당 숫자가 소수면서 n에서 소수를 뺀 값이 소수이면 count를 1씩 증가 

(두 소수의 순서만 다른 것은 같은 파티션으로 판단하기 때문에 for문은 0부터 n/2번까지 절반만 돌림)

 

 

정답 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


public 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));
     
    	int max = 1000000;
    	//false이면 소수 
        boolean prime[] = new boolean[max+1];
        
        prime[0] = true;
        prime[1] = true;
        
        for(int i=2; i<= Math.sqrt(max); i++)
        {
        	if(prime[i]) continue;
        	for(int j=i*i; j<=max; j+=i)
        	{
        		prime[j]=true;
        	}
        }
        
        int num = Integer.parseInt(br.readLine());
        
        for(int i=0; i<num; i++)
        {
        	int count = 0;
        	int n = Integer.parseInt(br.readLine());
        	for(int j=2; j<=n/2; j++)
        	{
        		if(!prime[j] && !prime[n-j])
        			count++;
        	}
        	bw.write(count+"");
        	bw.newLine();
        }

        
        bw.flush();
        bw.close();
        
    }
}