[백준] 1929번 : 소수 구하기, 에라토스테네스의 체 (Kotlin)

에라토스테네스의 체

에라토스테네스의 체는 2~N의 수 중 소수를 판별하는 알고리즘입니다.

해당 알고리즘의 정의를 요약하자면 2부터 N까지의 수 중 2의 배수, 3의 배수, 4의 배수 ... 제곱근N의 배수까지 나눠서 걸러지지 않고 남아 있는 수들이 모두 소수가 된다는 내용입니다.

 

기존의 소수를 구하는 방식인 소수는 1과 자기 자신만을 약수로 가진다는 조건에 따라 범위 내의 모든 수를 판별하는 방식보다 훨씬 실행속도가 빠르다는 장점이 있습니다.

 

☞ 예를 들어, 2부터 16까지의 수 중 소수를 찾아보겠습니다.

16의 제곱근은 4이므로 2부터 4까지의 배수를 검사합니다.

2의 배수인 4, 6, 8, 10, 12, 14, 16 / 3의 배수인 6, 9, 12, 15 / 4의 배수인 8, 12, 16 가 모두 걸러져 2~16 사이의 소수는 2, 3, 5, 7, 11, 13임을 판별할 수 있습니다.

 

 

에라토스테네스의 체를 이용해 [백준 1929번 : 소수 구하기] 예제를 해결해 보겠습니다.

---

1929번: 소수 구하기

import kotlin.math.sqrt

fun main() {
    val (M,N) = readLine()!!.split(" ").map { it.toInt() }
    // 인덱스의 참, 거짓을 소수 판별 여부로 사용할 것
    val primeArr = Array<Boolean>(N+1) { true }
    primeArr[1] = false

    // i를 2부터 N의 제곱근까지 탐색
    for (i in 2..sqrt(N.toDouble()).toInt()) {
        if (primeArr[i]) {
            var j = 2
            // i의 배수가 N보다 작을 때 i의 배수를 소수에서 제거
            while (i*j <= N) {
                primeArr[i*j] = false
                j++
            }
        }
    }
    // 최종적으로 primeArr에 true로 남아있는 인덱스가 소수
    for (i in M..N) {
        if (primeArr[i]) {
            println(i)
        }
    }
}