백준 9020번 골드바흐의 추측 JAVA 구현해보기

---

```

백준 9020번 골드바흐의 추측 JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1.  백준 9020번 풀이

---

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

9020번: 골드바흐의 추측

 

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

 

백준 9020번은

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

 

골드바흐 수 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 = 100;

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

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

        for (int idx1 = 0; idx1 < testCase; idx1++) {

            int n = Integer.parseInt(br.readLine());
            int midN = n / 2;

            for (int idx2 = midN; idx2 > 1; idx2--) {
                if (isPrime[idx2] && isPrime[n - idx2]) {
                    sb.append(idx2).append(" ").append(n - idx2).append("\n");
                    break;
                }
            }
        }

        sb.setLength(sb.length() - 1);
        System.out.println(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;
    }
}

 

 

읽어주셔서 감사합니다

 

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

 

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

 

---