백준 6588 자바 - 골드바흐의 추측 (BOJ 6588 JAVA)

문제 : boj6588

 

 

1.

  홀수인 소수란 말은 그냥 2를 제외한 소수라는 의미이다. 2 말곤 전부 홀수인 소수이다. 아무튼 그러니 100만 이하의 소수를 모두 구해준다. 에라토스테네스의 체를 사용해 입력받기전에 미리 구해두면 각 케이스에 대해 해당 소수들을 써먹을 수 있으니 효율적이다.

 

  그리고 여러 방법이 있겠으나, 시간복잡도를 좀 손해보더라도 편하게 코드를 짜기 위해 TreeSet에 찾은 소수를 넣어두었다. 시간 복잡도에 중점을 두려면 소수를 hashSet에 넣고, 추가로 소수 순서대로 배열에 넣어두면 된다. 어차피 시간이 널널한 문제라 뭘 쓰던 상관없다. TreeSet은 set이므로 a+b = n을 찾을 때 a가 정해지면 b가 존재하는지 contains(n-a)로 확인할 수 있다. 또한 hashSet과 다르게 순서대로 들어가있으므로 iterator 사용 시 소수를 차례대로 찾을 수 있다.

 

 

2.

  이후 입력을 받으면서, 각 테스트 케이스에 대해 첫 소수인부터 시작해서 n-a가 존재할 때까지 찾는다. 찾지 못했다면 TreeSet에서 a를 다음 수(it.next())를 가르키도록 한다.

 

이렇게 가장 낮은 수부터 실행 시 가장 차이가 큰 부분부터 확인하고 찾았다면 거기서 끝내므로 'n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력' 부분은 자동으로 만족 가능하다. 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.TreeSet;

public class Main {
    private static final int MAX = 1000000;
    TreeSet<Integer> pn;

    private void initPrimeNum() {
        pn = new TreeSet<>();
        boolean[] arr = new boolean[MAX+1];
        int sqrtMax = (int) Math.sqrt(MAX);

        for (int base = 3; base <= sqrtMax; base+=2) {
            if (arr[base]) continue;
            int tmp = base+base;

            while (tmp <= MAX) {
                arr[tmp] = true;
                tmp += base;
            }
        }

        for (int i = 3; i <= MAX; i+=2) {
            if (!arr[i])
                pn.add(i);
        }
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder answer = new StringBuilder();
        initPrimeNum();

        int n;
        while (( n = Integer.parseInt(br.readLine()) ) != 0) {
            int a = 3;
            boolean chk = false;
            while (a <= MAX) {
                if (pn.contains(n-a)) {
                    chk = true;
                    answer.append(n).append(' ').append('=')
                            .append(' ').append(a).append(' ').append('+')
                            .append(' ').append(n-a).append('\n');
                    break;
                }
                a = pn.higher(a);
            }
            if (!chk)
                answer.append("Goldbach's conjecture is wrong.\n");
        }
        System.out.print(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}