BOJ 6588 골드바흐의 추측 [Java]

BOJ 6588 골드바흐의 추측

1. 문제 링크

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

2. 문제 해설

true이면 소수이고, false면 소수가 아닌 isPrime 배열을 만든다. 테스트 케이스의 범위가 6이상 1000000이하이므로 크기는 1000001로 지정해준다.
일단 isPrime 배열의 원소를 전부 true로 초기화해주고, 그 후 에라토스테네스의 체를 이용하여 소수가 아닌 수들은 false로 바꿔준다.

이제 골드바흐의 추측이 가능한지 아닌지를 판단해주는 impossible 함수에 대해 설명해보겠다.
impossible 함수는 n을 매개변수로 받고, n 이하의 짝수들을 전부 탐색하면서 두 짝수 소수의 합으로 나타낼 수 있으면 앞 쪽 소수를 반환한다.
두 짝수 소수의 합으로 나타낼 수 없으면 -1을 반환한다.

출력을 구현하는 방식에 대해 설명해보겠다.
문제의 조건에 따라 0이 입력될 때까지는 while문을 이용하여 계속 입력을 받다가, 0이 나오면 break한다.
입력 받은 정수를 impossible함수에 넣어준 후 나온 결과 값을 chk에 담는다.
chk값이 -1 이면 골드바흐의 추측이 불가능하고, 아니라면 가능한 경우이다.
위 조건에 맞게 출력해야하는 문자열을 출력해준다.

3. 코드 보기

import java.io.*;
 
public class Main
{
    static int maxVal = 1000000;
    static boolean[] isPrime = new boolean[maxVal + 1];
 
    static int impossible(int n)
    {
        for (int i = 2; i * 2 <= n; i++)
        {
            int a = i;
            int b = n - a;
            if (isPrime[a] && isPrime[b])
                return a;
        }
 
        return -1;
    }
 
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
 
        isPrime[1] = false;
        for (int i = 2; i <= maxVal; i++)
            isPrime[i] = true;
 
        for (int i = 2; i <= Math.sqrt(maxVal); i++)
        {
            if (isPrime[i] == true)
            {
                for (int j = 2; i * j <= maxVal; j++)
                    isPrime[i * j] = false;
            }
        }
 
        while (true)
        {
            int n = Integer.parseInt(br.readLine());
            if (n == 0)
                break;
            int chk = impossible(n);
            if (chk > 0)
                sb.append(n + " = " + chk + " + " + (n - chk) + "\n");
            else
                sb.append("Goldbach's conjecture is wrong.");
        }
 
        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}