[Kotlin] 백준 1456 : 거의 소수

문제 링크

1456번: 거의 소수

---

---

문제 해설

수의 범위가 주어졌을 때 해당 범위 내에서 소수의 거듭제곱이 되는 수의 개수를 찾는 문제다.

 

범위가 최대 \(10^{14}\)이지만 소수는 최대 \(10^{7}\) 범위 내에서만 찾으면 된다. 소수의 거듭제곱이 범위 내에 포함되는지를 찾아야하는데 \(10^{7}=\sqrt{10^{14}}\)이므로 \(10^7\)을 초과하는 소수는 거듭제곱을 하면 범위를 벗어나기 때문이다. 따라서 우선 에라토스테네스의 체를 이용하여 \(\sqrt{B}\) 이하인 소수를 모두 구한다.(코드의 getPrimes() 메소드)

 

이후 구해진 소수들을 순회하면서 주어진 범위 내에 소수의 거듭제곱이 포함되는지 확인해야하는데 여기서 주의해야할 점이 있다. \(10^7\)을 세제곱하면 \(10^{21}\)이 되어 Long 타입의 범위를 아득히 초과하기 때문에 오버플로가 발생할 수 있다. 따라서 오버플로를 방지하기 위한 별도의 로직이 필요하다.

 

오버플로를 방지하기 위한 로직은 여러 방법이 있겠지만, 필자의 경우에는 소수가 \(\left \lfloor \sqrt[3]{10^{14}} \right \rfloor=46,415\)보다 크면서 현재 검사하는 수가 \(10^{7}\)보다 클 때 다음 소수로 넘어가는 방식으로 구현했다.

---

Code

import kotlin.math.sqrt

fun main() = with(System.`in`.bufferedReader()) {
    val (a, b) = readLine().split(' ').map { it.toLong() }
    val primeNumbers = getPrimes(b)
    var count = 0

    for (prime in primeNumbers) {
        var num = prime
        while (num <= b) {
            if (prime > 46415 && num > 10_000_000) break
            num *= prime
            if (num in a..b) count++
        }
    }

    println(count)
}

private fun getPrimes(b: Long): List<Long> {
    val isPrime = BooleanArray(sqrt(b.toDouble()).toInt() + 1) { true }
    val sqrt = sqrt(isPrime.lastIndex.toDouble()).toInt()
    val resultList = mutableListOf<Long>()
    isPrime[0] = false
    isPrime[1] = false

    for (i in 2..sqrt) {
        if (isPrime[i]) {
            for (j in i * i..isPrime.lastIndex step i) isPrime[j] = false
        }
    }

    for (i in isPrime.indices) {
        if (isPrime[i]) resultList.add(i.toLong())
    }
    return resultList
}

---

참조 링크

[Kotlin/Java] 소수 찾기와 에라토스테네스의 체