[JAVA] 백준 17103번- 골든바흐 파티션

https://www.acmicpc.net/problem/17103

17103번: 골드바흐 파티션

 

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


public class Main{
    static int[] arr = new int[1000001];
    public static int partition(int n){

        int answer = 0;
        // 골든바흐 파티션 찾기
        for(int i=2; i<=n/2; i++){
            if(arr[i] != 1 && arr[n-i]!=1){
                answer++;
            }
        }
        return answer;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        // 에라토스테네스의 체
        for(int i=2; i<=Math.sqrt(arr.length); i++){
            for(int j=i*i; j<arr.length; j+=i){
                if(arr[j]==0) arr[j]=1;
            }
        }
        while(T-->0){
            int n = Integer.parseInt(br.readLine());
            System.out.println(partition(n));
        }
    }
}

 

 

에라토스테네스체로 소수가 아닌 것들을 배열에 1로 저장하고

partition 함수에서 배열을 탐색하며 숫자의 합이 n이 되고 소수가 아닌 두개의 숫자를 찾는다.

이 때, (7,3) (3, 7) 처럼 두 소수의 순서만 다른 숫자일 경우 같은 파티션이므로 탐색을 n/2까지만 한다.