백준 17103번 골드바흐 파티션 JAVA 구현해보기

---

```

백준 17103번 골드바흐 파티션 JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1.  백준 17103번 풀이

---

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

17103번: 골드바흐 파티션

 

골드바흐의 추측은 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이고 이러한 수를 골드바흐 수라고 합니다. 위의 두 소수는 골드바흐 파티션이라고 합니다.

 

백준 17103번은

난이도 실버 등급의 문제로서

 

골드바흐 수 N 이 주어질 때 N을 만들 수 있는 골드바흐 파티션의 개수를 구해주면 됩니다.

순서가 다른 두 소수 쌍은 같은 파티션으로 취급합니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

전에 만든 

findPrimeNumbers 메서드를 그대로 사용해서

문제 범위에 있는 소수들을 아리토스테네스의 체로 구해줍니다. 

 

그다음

테스트 케이스만큼 반복하는데

입력받은 골드바흐 수에

중간 지점부터 시작해서

차근차근 파티션을 찾고

찾은 경우

스트링 빌더에 넣어줍니다.

테스트 케이스가 끝나면

스트링 빌더를 출력합니다.

 

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

public class Main {
    final static int SQRT_PRIME_LIMIT = 1000;

    public static void main(String[] args) throws IOException {
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // find prime numbers
        final boolean[] isPrime = findPrimeNumbers();

        // input test case;
        int testCase = Integer.parseInt(br.readLine());

        // solution accumulation
        StringBuilder sb = new StringBuilder();

        // iterate over testCases
        for (int idx1 = 0; idx1 < testCase; idx1++) {
            int size = 0;
            int n = Integer.parseInt(br.readLine());
            int midN = n / 2;
            for (int idx2 = midN; idx2 > 1; idx2--) {
                if (isPrime[idx2] && isPrime[n - idx2]) {
                    size++;
                }
            }
            sb.append((size)).append("\n");
        }
        sb.setLength(sb.length() - 1);
        System.out.print(sb);
        br.close();
    }

    private static boolean[] findPrimeNumbers() {
        int sqrtPrimeLimitNum = SQRT_PRIME_LIMIT;
        int PrimeLimitNum = sqrtPrimeLimitNum * sqrtPrimeLimitNum;
        final boolean[] isPrime = new boolean[PrimeLimitNum];
        Arrays.fill(isPrime, Boolean.TRUE);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i <= sqrtPrimeLimitNum; i++) {
            if (isPrime[i]) {
                for (int j = i; j < PrimeLimitNum; j += i) {
                    if (isPrime[j] && i != j) {
                        isPrime[j] = false;
                    }
                }
            }
        }
        return isPrime;
    }
}

//codemasterkimc.tistory.com/search/파티션 [김씨의 코딩 스토리]

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---