[알고리즘] 에라토스테네스의 체

정의

수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다.

에라토스테네스 - 위키백과, 우리 모두의 백과사전

알고리즘

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.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val number = br.readLine().toInt()

    // 입력으로 들어온 수까지 모든 수를 소수라고 초기화 한다.
    val prime = BooleanArray(number + 1) { true }

    // 입력된 수의 제곱근을 구한다.
    val sqrt = Math.sqrt(number.toDouble()).toInt()

    println("sqrt : $sqrt")

    // 2부터 제곱근 까지 탐색한다.
    for (i in 2..sqrt) {
        // 소수가 아니므로 다음 탐색을 한다.
        if (!prime[i]) continue

        var j = 2
        while (i * j <= number) {
            if (prime[i * j]) prime[i * j] = false
            j++
        }
    }

    println("===== Result =====")
    for (i in 2..number) {
        if (prime[i]) print("$i ")
    }
    println()
}