[Algorithm] 백준온라인저지 6588번(BOJ 6588) 골드바흐의 추측 Java 풀이!! (에라토스테네스의 체)

---

안녕하세요 Coding-Knowjam입니다.

이번에 풀어볼 문제를 백준 온라인 저지에 있는 6588번 골드바흐의 추측입니다.

 

1. 문제 설명

문제를 설명하기에 앞서 아래 링크로 가셔서 문제를 읽고 오시길 바랍니다.

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

 

해당 문제는 백만 이하의 숫자 중 4보다 큰 짝수를 홀수 소수의 합으로 나타내는 문제입니다.

문제에서 요구하는 두 개의 수를 구하는 것과 출력 서식에 맞게 출력하는 건 그냥 내용에 맞춰서 구현을 하면 됩니다.

중요한 건 백만 이하의 숫자에서 소수를 찾아내는 것이며, 소수 찾기의 대표적인 알고리즘 에라토스테네스의 체를 사용해서 문제를 풀어야 합니다.

에라토스테네스의 체 알고리즘만 알고 계시다면 어렵지 않게 풀 수 있습니다.

그럼 바로 코드를 작성해보겠습니다.

 

2. Java로 문제 풀이

package study.blog.codingnojam.algorithm;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class BOJ_6588 {

    // 백준온라인저지 6588번 골드바흐의 추측 Java 풀이
    public static void main(String[] args) throws IOException {

        // 입출력을 위한 객체
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 소수 판별에 사용할 배열
        // 인덱스를 숫자자체로 사용하기 위해 길이 1추가
        // 백만이하의 숫자에 대해서만 골드바흐의 추측을 검증할꺼니까 백만일로 길이설정
        boolean[] arr = new boolean[1000001];
        // 0과 1은 소수가 아닙니다.
        arr[0] = true;
        arr[1] = true;

        // 에라토스테네스의 체를 사용해서 소수 판별
        for (int i = 2; i < 1001 ; i++) {
            // 소수가 아니면 다음 숫자로 넘어감
            if (arr[i]) {
                continue;
            }
            // 소수의 배수들을 모두 체크
            // true : 소수아님, false : 소수
            for (int j = i * i; j <arr.length ; j = j + i) {
                arr[j] = true;
            }
        }

        // 테스트케이스가 10만개까지이므로 반복문은 10만번으로 설정
        for(int i =0; i < 100000; i++){
            // 주어진 짝수 받기
            int N = Integer.parseInt(br.readLine());
            // 주어진 수가 0이면 반복문의 더 이상 남은 케이스가 없으므로 종료
            if (N == 0) {
                break;
            }

            // 에라토스테네스의 체를 사용해서 소수를 판별한 배열로 반복문사용
            // 문제에서 두수의 차가 가장 큰 경우를 출력해야한다고 했으므로
            // 배열의 끝에서부터 인덱스를 줄어가면서 반복문 실행
            // 여기서 배열의 인덱스는 숫자 그 자체를 의미함
            for (int j = arr.length-1; j >= 3; j--) {
                // 주어진 수보다 현재 배열에서 읽은 숫자가 더 큰 경우
                if (j >= N) {
                    // 그냥 단순하게 모든 반복문을 루프 돌아도 되지만
                    // 그렇게 되면 시간초과 판정을 받을 확률이 높아집니다.
                    // 그러므로 주어진 수보다 낮은 경우부터 시작해야 합니다.
                    // 이를 위해 배열에서 꺼낼 인덱스를 주어진 수와 같은 수로 변경
                    // 이제 다음 반복문 실행할 때 증감식에 의해서 더 낮은 숫자부터 시작
                    j = N;
                    continue;
                }
                // 배열에서 읽은 숫자가 소수가 아닌경우 다음 수로 넘어감
                if (arr[j]) {
                    continue;
                }

                // 배열에서 읽은 숫자가 주어진 수보다 작고, 소수인경우
                // 주어진 수 - 현재 읽은 소수 = 두수의 차를 구함
                int k = N - j;

                // 두수의 차가 소수라면 문제에서 요구하는 서식대로 출력문 저장
                if (!arr[k]) {
                    String tempN = String.valueOf(N);
                    String tempK = String.valueOf(k);
                    String tempJ = String.valueOf(j);
                    bw.write(tempN + " = " + tempK + " + " + tempJ);
                    bw.newLine();
                    break;
                }

                // 반복문의 마지막까지 실행을 했을 경우
                // 주어진수를 소수의 합으로 표현할 수 없으므로
                // 문제에서 요구하는 출력문 저장
                if (j == 3) {
                    bw.write("Goldbach's conjecture is wrong.");
                    bw.newLine();
                }
            }
        }
        // 최종 출력
        bw.flush();
    }
}

 

작성한 코드 라인마다 주석을 상세히 달아놓았으니 설명을 부가적으로 하지 않겠습니다.

한 가지 유의해야 할 점은 52라인부터 시작되는 if문인데요

문제에서 요구하는 시간은 1초입니다.

그러므로 반복문을 돌리는 횟수를 최소화시켜야 합니다.

이를 위해 주어진 짝수보다 작은 수 중 가장 큰 소수부터 반복문을 실행할 수 있도록 반복문의 인덱스 값을 중간에 변경해주었습니다.

이 부분만 주의하시면 나머지는 주석에 쓰인 설명을 통해서 이해하실 수 있을 거라 생각합니다.

감사합니다.

---