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

---

```

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

```

이번 글을 통해 배워갈 내용

1.  백준 6588번 풀이

---

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

6588번: 골드바흐의 추측

 

 

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

 

백준 6588번은

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

 

골드바흐 수 N 이 주어질 때 N을 만들 수 있는 골드바흐 파티션 중에 가장 두 수의 차이가 큰 수들을 찾아서

N = A + B 형식으로 출력해주고

0을 입력받으면 종료해주면 됩니다.

 

---

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

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

---

전에 만든 

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

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

 

그다음

반복하는데

입력받은 골드바흐 수에

시작 지점부터 시작해서

차근차근 파티션을 찾고

찾은 경우

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

0을 입력받으면 break하고

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

 

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();

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

        // iterate over testCases
        while (true)
        {
            int n = Integer.parseInt(br.readLine());
            if (n == 0){
                break;
            }
            int midN = n / 2;
            for (int idx2 = 3; idx2 <= midN; idx2++) {
                if (isPrime[idx2] && isPrime[n - idx2]) {
                    sb.append(n).append(" = ").append(idx2).append(" + ").append(n-idx2).append("\n");
                    break;
                }
            }
        }
        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/파티션 [김씨의 코딩 스토리]

 

읽어주셔서 감사합니다

 

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

 

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

 

---