BOJ 6588. 골드바흐의 추측

BOJ 6588. 골드바흐의 추측

풀이

골드바흐의 추측

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

먼저 소수를 찾아야 하므로
에라 토스트 테네스의 체 알고리즘을 활용하여 범위 내의 모든 소수를 찾는다.
그리고 !check[a] && !check[b] 조건을 만족하는 a와 b를 찾는다.

Java

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int end = 1000000;

        boolean[] check = new boolean[end + 1];
        check[1] = true;

        for (int i = 2; i <= end; i++) {
            for (int j = 2; i * j <= end; j++) {
                if (!check[i * j]) {
                    check[i * j] = true;
                }
            }
        }

        while (true) {
            int n = sc.nextInt();
            if (n == 0)
                break;
            for (int i = 2; i * 2 <= n; i++) {
                int a = i;
                int b = n - a;
                if (!check[a] && !check[b]) {
                    sb.append(n + " = " + a + " + " + b + "\n");
                    break;
                }
            }
        }
        System.out.println(sb);
        sc.close();
    }
}

Kotlin

import java.lang.StringBuilder

fun main() {
    val sb = StringBuilder()
    val end = 1000001
    val check = BooleanArray(end + 1) { false }
    for (i in 2..end) {
        if (!check[i]) {
            var j = 2
            while (i * j <= end) {
                check[i * j] = true
                j++
            }
        }
    }

    while (true) {
        val n = readLine()!!.toInt()
        if (n == 0) break
        for (i in 2..n / 2) {
            val a = i
            val b = n - a
            if (!check[a] && !check[b]) {
                sb.append("$n = $a + $b\n")
                break
            }
        }
    }
    println(sb)
}

풀이소스

github.com/beomjo/algorithm-study/blob/main/BOJ/java/6588.java github.com/beomjo/algorithm-study/blob/main/BOJ/kotlin/6588.kt