[Kotlin] 소수 구하기 - 에라토스테네스의 체

1 이상 n이하의 소수를 오름차순으로 출력하는 프로그램을 작성해 보세요.

 

소수 판별에서 에라토스테네스의 체 기법이 많이 활용되고 있습니다.
에라토스테네스의 체란?

1. 2부터 n까지의 모든 숫자를 나열합니다.
2. 현재 숫자를 소수로 표시하고, 현재 숫자의 배수를 모두 지웁니다.
3. 남아있는 숫자 중에서 다음 소수를 선택하고 2번 과정으로 돌아갑니다.
4. n의 제곱근까지 반복하면 모든 소수가 남습니다.

val isPrime = BooleanArray(n + 1) { true }
isPrime[0] = false
isPrime[1] = false

일단 모든 값을 소수라고 가정해 놓고 소거법 시키는 것과 비슷합니다.

0과 1은 소수가 아니므로 false로 설정합니다.

 

for (i in 2..n) {
    if (isPrime[i]) {
        for (j in i * 2..n step i) {
            isPrime[j] = false
        }
    }
}

2부터 주어진 n까지 반복하며 그에 대한 배수가 존재한다면 false로 소수가 아님을 명시해 줍니다.

 

return isPrime.indices.filter { isPrime[it] }

마지막으로 소수인 값만 필터링합니다.

 

import java.util.Scanner

fun findPrimesUpTo(n: Int): List<Int> {
    if (n < 2) return emptyList()

    val isPrime = BooleanArray(n + 1) { true }
    isPrime[0] = false
    isPrime[1] = false

    for (i in 2..n) {
        if (isPrime[i]) {
            for (j in i * 2..n step i) {
                isPrime[j] = false
            }
        }
    }

    return isPrime.indices.filter { isPrime[it] }
}

fun main() {
    val scanner = Scanner(System.`in`)
    val n = scanner.nextInt()
    val primes = findPrimesUpTo(n)
    println(primes.joinToString(" "))
}