[백준] 1929번: 소수 구하기 - Kotlin[코틀린]

문제

 

1929번: 소수 구하기

 

---

풀이

 

 어떤 수가 소수인지 알기 위해서 아래 코드로 판별할 수 있지만, 범위 내에 모든 수를 아래와 같은 방법으로 판별한다면 비효율적이고 이 문제에서 시간초과가 발생한다.

    for(i in start .. end) {
        var cnt = 0
        for(j in 1..i) {
            if(i%j==0) {
                cnt++
            }
        }
        if(cnt==2) {
            println(i)
        }
    }

 

 대신 에라토스테네스의 체를 이용하여 해결할 수 있다. 에라토스테네스의 체는 범위 내에서 소수의 배수는 모두 지워가는 방식이다.

 

이미지 출처 - 위키백과

 

 2의 배수, 3의 배수, 5의 배수 .. 의 순서대로 소수가 아닌 수들을 지운다. 그림의 경우에 $11^2$ 이 마지막 숫자인 120보다 크기 때문에 11보다 작은 소수의 배수들만 지워도 충분하다.

 

---

코드

 

import kotlin.math.sqrt

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val sb = StringBuilder()

    val (start, end) = br.readLine().split(' ').map { it.toInt() }

    val prime = BooleanArray(end + 1)
    prime[1] = true

    for(i in 2 .. sqrt(end.toDouble()).toInt()) { // end의 제곱근보다 작은 수의 배수까지 계산
        if(prime[i]) continue

        for(j in i*i .. end step +i) { // i의 배수
            prime[j] = true
        }
    }

    for(i in start .. end) {
        if(!prime[i]) {
            sb.append(i).append('\n')
        }
    }

    bw.write("$sb")
    bw.flush()
    bw.close()
    br.close()
}