[Kotlin] BOJ 1929. 소수 구하기 (ft. 에라토스테네스의 체)

출처

https://www.acmicpc.net/problem/1929

 

문제

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

 

입력

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

 

출력

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

 

 

 

풀이

1. 소수란?

1과 자기 자신만을 약수로 가지는 수

ex) 2, 3, 13....

 

2. 소수를 구하는 방법?

a. 각 수마다 for문으로 소수인지 아닌지 구하는 방법 -> 하나하나 구해야 하므로 시간복잡도가 높다! O(N)

 

b. 에라토스테네스의 체 -> 제곱근까지만 순회하므로 시간복잡도가 낮다! O(NlogN)

 

에라토스테네스의 체

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. (보라색)

 

풀이

import java.io.BufferedReader
import kotlin.math.sqrt

fun main() = with(System.`in`.bufferedReader()) {
    val input = readLine().split(" ").map { it.toInt() }
    getPrime(input[0], input[1])
}
private fun getPrime(m : Int, n: Int){
    var isPrime = BooleanArray(n+1) {true}
    // 제곱근까지만 판별
    val sqrt = sqrt(n.toDouble()).toInt()
    isPrime[1] = false
    // 아리토스테네스의 체 원리
    for (i in 2..sqrt) {
        if (!isPrime[i]) continue
        else {
            var j = 2
            while (i*j <= n) {
                if (isPrime[i*j]) isPrime[i*j] = false
                j++
            }
        }
    }

    for (i in m..n) {
        if (isPrime[i]) println(i)
    }
}