[백준 JAVA] 17103번 풀이 - 골드바흐 파티션 (골드바흐의 추측)

package quiz;

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

/**
 * 골드바흐 파티션
 */
public class Main {

    static int[] primeArr = new int[1000001];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());

        makingPrimeArr();

        for ( int i = 0; i < testCase; i++ ){
            int n = Integer.parseInt(br.readLine());
            int sum = 0;
            int count = 0;

            for ( int j = 2; j <= n/2; j++ ){
                //j 와 n-j가 소수이면서, j+(n-j) 가 n이 되는 경우의 수 . 
                if ( primeArr[j] != 0 && primeArr[n-j] != 0 ) count++;
            }
            System.out.println(count);
        }
    }

    public static void makingPrimeArr(){
        for ( int i = 0; i <= 1000000; i++ ) {
            primeArr[i] = i;
        }

        //소수 배열 만들기. 배수 지우기
        for ( int i = 2; i < Math.sqrt(1000000); i++ ){
            if ( primeArr[i] == 0 ) continue;

            for ( int j = i + i; j <= 1000000; j+= i ){
                primeArr[j] = 0;
            }
        }
    }


}

🔥 골드바흐의 추측 : 오래전부터 알려진 정수론의 미해결 문제로, 2보다 큰 짝수는 두 개의 소수의 합으로 표시할 수 있다는 것이다. (출처 : 위키백과)

풀이

1. 에라토스테네스의 체로 소수 배열을 만든다. 

2. 소수 배열에서 i 와 n-i 의 합의 n과 같으면, 골드바흐의 파티션에 들어간다. 

 

가령, n = 12 일 때, 

i = 2	n-i = 10	10이 소수x	X
i = 3	n-i = 9	9가 소수x	X
i = 4	n-i = 8	둘 다 소수x	X
i = 5	n-i = 7	둘 다 소수, 5+7=12 (n)	O
i = 6	n-i = 6	6이 소수X	X

으로 n=12 에서 골드바흐 파티션 개수는 1이다. 

같은 숫자의 다른 순서는 취급하지 않기 위해, 골드바흐 파티션을 찾는 범위는 n이 아닌, n/2 로 설정한다. 

 

 

💬 [알고리즘] 에라토스테네스의 체 

https://backshren20.tistory.com/646

[알고리즘] 에라토스테네스의 체 란? (Prime 소수 구하기)