[백준] 1929 소수구하기 (Kotlin)

📌 Mac M2 pro 사용

1. 문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

• 입력(첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.)

    3 16
  

• 출력(한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.)

    3
    5
    7
    11
    13
  

2. 풀이

  fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bfWriter = BufferedWriter(OutputStreamWriter(System.out))
    val (start, end) = readLine().split(' ').map { it.toInt() }

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

    for(i in 2 .. sqrt(end.toDouble()).toInt()) {
      if(prime[i]) continue

      for(j in i*i .. end step i) {
          prime[j] = true
      }
    }

    for(i in start .. end) {
      if(!prime[i]) {
          bfWriter.write("$i\n")
      }
    }

    bfWriter.flush()
    bfWriter.close()
    close()
  }

처음엔 범위 내에 모든 수를 소수인지 검사하는 코드를 짜려고 하였으나 그렇게 문제를 해결하면 시간 초과가 될 것 같아 에라토스테네스의 체를 이용해서 코드를 작성하였다. 에라토스테네스의 체는 아래와 같다.