[Kotlin] 백준 9020 : 골드바흐의 추측

문제 링크

9020번: 골드바흐의 추측

---

---

문제 해설

10,000 이하의 짝수 \(n\)이 주어졌을 때, \(n\)을 차이가 가장 작은 두 소수의 합으로 나타내야 한다. 기본적으로는 4948번 문제와 접근 방법이 비슷하다. 모든 테스트 케이스 중 가장 큰 \(n\) 이하의 모든 소수를 탐색한 후 각 테스트 케이스에 대해 주어진 문제의 계산을 수행하면 된다.

 

문제에 \(n\)의 골드바흐 파티션을 구하면서 두 소수의 차이가 가장 작은 경우를 출력하라는 조건이 걸려있다. 어떤 짝수 \(x\)를 두 수의 합으로 나타낼 때 가장 차이가 적은 경우는 \(\frac{x}{2}\)를 두 번 더한 경우이다. 따라서 각 테스트 케이스로 주어진 입력의 절반부터 해당 입력 - 2까지 반복문을 이용하여 두 소수의 합으로 나타나는 경우가 발견되면 해당 결과를 출력하고 다음 케이스로 넘어가면 된다.

---

Code

import kotlin.math.sqrt

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    val cases = ArrayList<Int>()
    var max = 0
    // 각 테스트 케이스를 추가하면서 테스트 케이스의 최대값 갱신
    repeat(readLine().toInt()) {
        cases.add(readLine().toInt().also { max = maxOf(max, it) })
    }
    // 테스트 케이스의 최대값 이하인 모든 소수 탐색
    val isPrime = BooleanArray(max + 1)
    isPrime[0] = true
    isPrime[1] = true
    val sqrt = sqrt(max.toDouble()).toInt()
    for (i in 2..sqrt) {
        if (!isPrime[i]) {
            for (j in i * i..max step i)
                isPrime[j] = true
        }
    }
    // 각 테스트 케이스별로 골드바흐 파티션으로 나타나는 경우를 탐색하여 출력
    for (t in cases) {
        for (i in t / 2..t - 2) {
            // 골드바흐 파티션을 발견하면 다음 테스트 케이스로 넘어감
            if (!isPrime[i] && !isPrime[t - i]) {
                bw.write("${t - i} $i\n")
                break
            }
        }
    }
    bw.close()
}