[백준] 17103_골드바흐 파티션 / 에라토스테네스의 체 알고리즘

 

Sliver

 

문제

골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

 

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

 

출력

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

 

---

 

풀이

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);    
        StringBuilder sb = new StringBuilder();
        int N = sc.nextInt();
        int[] nums = new int[N];
        int max = 0;
        
        for(int i=0 ; i<N; i++){
            nums[i] = sc.nextInt();
            max = Math.max(max, nums[i]);
        }

        boolean[] arr = new boolean[max+1];
        for(int i=2; i<=max; i++){
            if(!arr[i])
                for(int j=2; i*j<=max; j++) arr[i*j] = true;
        }

        for(int num : nums){
            int count = 0;
            for(int j=2; j<=num/2; j++){
                if(!arr[j] && !arr[num-j]) count ++;
            }
            sb.append(count).append("\n");
        }
        System.out.print(sb);
        sc.close();

    }  
}

 

해결방법

1. 입력받은 수 중 가장 큰 값 max를 구하고, max+1 크기의 배열을 생성한 후 에라토스테네스의 체 알고리즘을 사용하여 소수를 판별하는 배열을 만들어주었다. 

2. 이후 입력받은 숫자 별 골드바흐 파티션 수를 구해주었다. 

 

---

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