백준 - 4948 베르트랑 공준

문제

4948 베르트랑 공준

답

kotlin code

fun main() {
    val inputs = readInputs()

    val isPrimeNumbers = getIsPrimeNumbers(inputs.maxOf { it } * 2)

    printOutput(inputs, isPrimeNumbers)
}

fun printOutput(inputs: MutableList<Int>, primeNumbers: BooleanArray) = inputs.forEach { println((it + 1..it * 2).count { x -> primeNumbers[x] }) }

fun getIsPrimeNumbers(to: Int): BooleanArray {
    val isPrimeNumbers = BooleanArray(to + 1) { true }
    isPrimeNumbers[0] = false
    isPrimeNumbers[1] = false
    val max = kotlin.math.sqrt(isPrimeNumbers.size.toDouble()).toInt()
    for(index in (2..max)) {
        if(!isPrimeNumbers[index]) continue
        for(i in ((index * index)until isPrimeNumbers.size) step index) {
            isPrimeNumbers[i] = false
        }
    }
    return isPrimeNumbers
}

fun readInputs(): MutableList<Int> {
    val inputs = mutableListOf<Int>()
    while (true) {
        val input = readln().trim()
        if(input == "")  continue
        if(input == "0") return inputs
        inputs.add(input.toInt())
    }
}

Reference

소수 (수론)

에라토스테네스의 체