에라토스테네스의 체 in Kotlin

📌 에라토스테네스의 체란 무엇인가?

가장 간단하고 빠르게 자연수 n 이하의 모든 소수를 찾는 방법으로,
마치 체로 치듯이 수를 걸러낸다고 하여 '체'라는 이름이 붙었다고 한다.

📌 에라토스테네스의 체 구현

자연수 n 이하의 모든 소수를 찾는다고 하면,

1. 먼저 boolean 배열(isPrime)을 생성한다. isPrime[i]가 의미하는 것은 자연수 i가 소수인지 여부이다.
2. 0과 1을 제외하고 isPrime을 모두 true로 초기화한다. (모든 수가 소수라고 가정한다)
3. 2부터 n까지 반복문을 돌면서 isPrime이 true인 경우(소수인 경우), 그 수의 배수들은 모두 소수가 아니므로 isPrime을 false로 표시한다.

📌 N까지 자연수 중 소수 찾기

// 1. 일단 모든 수가 소수라고 가정
val isPrime = BooleanArray(N) { true }

isPrime[0] = false; isPrime[1] = false
var i = 2
while (i * i <= N) {
	if (!isPrime[i]) continue
    
    // 2. i가 소수일 때 (i * i)부터 N까지 수 중 i의 배수는 소수가 아니다.
    var j = i * i
    while (j <= N) {
        isPrime[j] = false
        j += i
    }
    
    i++
}