[코틀린] 에스토스테네스의 체 (소수 찾기)

백준 문제를 풀던 중 에스토스테네스의 체를 이용하는 문제를 풀게 되었다.

Kotlin으로 작성한 템플릿을 기억해두기 위해 간단하게 포스팅 한다. 

private fun sosu(n: Int) : IntArray{
    val isSosu = BooleanArray(n+1) {true}
    for (i in 2 .. kotlin.math.sqrt(n.toDouble()).toInt()) {
        if (isSosu[i]) {
            var j = 2
            while (i * j <= n) isSosu[i * j++] = false
        }
    }

    val list = mutableListOf<Int>()
    for (i in 2 .. n) if (isSosu[i]) list.add(i)

    return list.toIntArray()
}

알고리즘 원리는 단순하다. for 문을 돌며 소수가 아닌 것을 false로 변경해주는 방식이다. 알고리즘 원리 자체는 어디든 많이 적혀있기 때문에 본 블로그에서는 생략한다!