백준 9020번 문제풀이 - 골드바흐의 추측

백준 9020번 문제

 

 

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

9020번: 골드바흐의 추측

 

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하는 문제이다. 

짝수 n이 주어지기 때문에 n을 2로 나누고 나눈 수가 소수이면 두 가지 소수로 출력하고 소수가 아닐 경우 2로 나눈 수를 1씩 더 해가고 n에서 빼서 두 수 모두 소수인지를 확인하면 된다.

 

 

 

 

 

 

코딩

public class Goldbach {
    public static boolean[] prime = new boolean[10001];
    // 소수를 구하는 메소드
    static void get_prime() {
        Arrays.fill(prime, true);
        prime[0] = prime[1] = false;
        for (int i = 0; i <= Math.sqrt(prime.length); i++) {
            if (!prime[i]) continue;
            for (int j = i * i; j < prime.length; j += i) {
                prime[j] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        get_prime();// 소수는 true, 아니면 false
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            if (prime[num / 2]) { // n의 1/2이 소수면 두 수로 출력
                sb.append(num / 2 + " " + num / 2).append('\n');
            } else { // n/2가 소수가 아닐 경우
                int gol = num / 2;
                while (true) {
                    gol++;
                    if (prime[gol] && prime[num - gol]) // 둘 다 소수일 경우 break
                        break;
                }
                sb.append(num - gol + " " + gol).append('\n');
            }
        }
        System.out.println(sb);
    }
}

 

 

 

 

 

 

결과

 

 

 

 

 

느낀 점

알고리즘은 잘 작성했지만 코드를 작성할 때 아쉬운 부분이 많았음. while문의 무한루프 활용하는 법에 대한 이해와 for문의 무한루프 활용 등에 대한 이해를 높일 필요가 있다는 것을 느꼈음.