[백준] 골드바흐의 추측

[yu-heejin]

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

[yu-heejin]

import java.io.*;

public class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = -1;

        while (n != 0) {
            n = Integer.parseInt(br.readLine());

            if (n == 0) break;

            // 두 수의 차가 가장 큰 수를 출력하기 위함
            int a = 2;
            boolean isWrong = true;

            while (a <= n) {
                int b = n - a;

                // 두 수가 소수인 경우
                if (isPrime(a) && isPrime(b)) {
                    System.out.println(n + " = " + a + " + " + b);
                    isWrong = false;
                    break;
                }

                a++;
            }

            if (isWrong) {
                System.out.println("Goldbach's conjecture is wrong.");
            }
        }
    }

    private static boolean isPrime(int n) {
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }

        return true;
    }
}

[yu-heejin]

import java.io.*;
import java.util.Arrays;

public class Main {

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

        while (true) {
            int n = Integer.parseInt(br.readLine());

            if (n == 0) break;

            // 해당 수에 대한 에라토스테네스 알고리즘
            boolean[] isPrime = new boolean[n + 1];

            Arrays.fill(isPrime, true);

            isPrime[0] = false;
            isPrime[1] = false;

            for (int i = 2; i <= Math.sqrt(n); i++) {
                if (isPrime[i]) {
                    for (int j = i * i; j <= n; j += i) {
                        isPrime[j] = false;
                    }
                }
            }

            // 두 수의 차가 가장 작은 수
            int a = 2;
            boolean isWrong = true;

            while (a <= n) {
                int b = n - a;

                // 두 수가 모두 소수인 경우
                if (isPrime[a] && isPrime[b]) {
                    System.out.println(n + " = " + a + " + " + b);
                    isWrong = false;
                    break;
                }

                a++;
            }

            if (isWrong) {
                System.out.println("Goldbach's conjecture is wrong.");
            }
        }
    }
}