[Kotlin] 백준 4948 : 베르트랑 공준

문제 링크

4948번: 베르트랑 공준

---

---

문제 해설

어떤 자연수 \(n\)이 주어졌을 때 \(n\) 초과, \(2n\) 이하인 소수의 개수를 구해야하는 문제다.

 

어떤 수 \(x\) 이하의 모든 소수를 구하는 방법은 에라토스테네스의 체를 이용하는 방법이 있다. 이 문제도 에라토스테네스의 체를 이용하면 손쉽게 해결할 수 있다.

 

문제의 조건에 따르면 \(n\)의 최대값은 123,456이고, \(2n\) 이하인 소수의 개수를 구해야하므로 최악의 경우에는 246,912 이하인 소수를 구해야 한다. 여러 테스트 케이스를 입력받지만 246,912 이하인 소수 중 각 테스트 케이스에 해당하는 구간에 있는 소수의 개수를 출력하면 한 번의 계산으로 모든 테스트 케이스의 답을 얻을 수 있다.

 

따라서 에라토스테네스의 체를 이용하여 246,912 이하인 모든 소수를 구하고 각 테스트 케이스에 해당하는 구간만 잘라서 답을 출력하면 된다.

---

Code

import kotlin.math.sqrt

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    val cases = ArrayList<Int>()
    // 0이 입력될 때까지 모든 입력을 리스트에 저장
    while (readLine().also { cases.add(it.toInt()) } != "0") {}
    // 마지막에 입력된 0 제거
    cases.removeAt(cases.lastIndex)
    val max = 123456 * 2	// 최대치
    // max 이하의 모든 소수 탐색
    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
        }
    }
    // isPrime을 각 테스트케이스에 대한 구간만큼 자른 리스트에서 소수의 개수를 카운트하여 출력
    for (t in cases) {
        bw.write("${isPrime.slice(t + 1..2 * t).count { !it }}\n")
    }
    bw.close()
}

---

참조 링크 : [Kotlin/Java] 소수 찾기와 에라토스테네스의 체