[Algorithm/Kotlin] 에라토스테네스의 체(Sieve of Eratosthenes) 쉽게 이해하기

 

에라토스테네스의 체는 특정 범위에서 소수를 빠르고 효율적으로 구하는 방법입니다.

작은 소수의 배수를 제거함으로써 소수만 남기는 아이디어를 기반으로 합니다.

이 글에서는 코드와 함께 이해한 내용을 정리 해 두도록 하겠습니다.

---

에라토스테네스의 체의 핵심 동작

1. i의 범위 제한: i in 2..Math.sqrt(limit.toDouble()).toInt()

이 범위는 왜 필요한가?

• 소수의 배수 제거는 대칭적으로 이루어집니다.
  • 예: 16의 약수는 (2,8),(4,4)처럼 대칭적으로 나타납니다.
  • 따라서 sqrt(limit)​까지만 확인하면 충분합니다.
  • sqrt(16) = 4이므로 i=2,3,4까지만 반복하면 됩니다.

코드 예제

val limit = 16
for (i in 2..Math.sqrt(limit.toDouble()).toInt()) {
    println("i = $i")
}

 

실행 결과:

i = 2
i = 3
i = 4

 

정리:

• i의 범위를 2부터 sqrt(limit)​까지 제한하여 불필요한 반복을 줄입니다.

2. 배수 제거: i * i..limit step i

이 부분은 무엇을 하나요?

• i^2부터 i의 배수를 제거합니다.
• 왜 i^2부터 시작하나요?
  • i보다 작은 배수는 이미 이전 숫자에서 제거되었기 때문입니다.
  • 예: i=3 일 때:
    • 3×2=6: 이미 i=2에서 제거됨.
    • 3×3=9: i^2부터 시작해야 함.

코드 예제

val i = 2
val limit = 16
for (j in i * i..limit step i) {
    println("j = $j")
}

 

실행 결과:

j = 4
j = 6
j = 8
j = 10
j = 12
j = 14
j = 16

• 시작 값: i^2=4
• 끝 값: limit=16
• 증가 간격: step=i=2

다른 예제: i=3

val i = 3
val limit = 16
for (j in i * i..limit step i) {
    println("j = $j")
}

 

실행 결과:

j = 9
j = 12
j = 15

3. 전체 흐름 정리

예제: limit=16

1. i=2:
   •    2는 소수.
   •    제거 대상: 4,6,8,10,12,14,16.
2. i=3:
   •    3은 소수.
   •    제거 대상: 9,12,15 (이미 제거된 숫자는 제외).
3. i=4:
   •    4는 소수가 아님(이미 제거됨).
   •    반복하지 않음.

최종 구현 코드

fun sieveOfEratosthenes(limit: Int): List<Int> {
    val isPrime = BooleanArray(limit + 1) { true }
    isPrime[0] = false // 0은 소수가 아님
    isPrime[1] = false // 1은 소수가 아님

    for (i in 2..Math.sqrt(limit.toDouble()).toInt()) {
        if (isPrime[i]) {
            for (j in i * i..limit step i) {
                isPrime[j] = false
            }
        }
    }

    return isPrime.mapIndexed { index, prime -> 
        if (prime) index else null 
    }.filterNotNull()
}

fun main() {
    println(sieveOfEratosthenes(30)) // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
}

 

코드 설명

1. 배열 초기화:
   •    BooleanArray(limit + 1)을 사용해 0부터 limit까지 모든 숫자를 소수(true)로 가정합니다.
   •    0과 1은 소수가 아니므로 false로 설정합니다.
2. 소수의 배수 제거:
   •    i가 소수라면, i의 제곱부터 n까지 i 간격으로 숫자를 제거합니다.
   •    i보다 작은 배수는 이미 제거되었으므로 검사하지 않습니다.
3. 소수만 반환:
   •    mapIndexed로 true인 숫자의 인덱스를 추출하고, filterNotNull로 유효한 숫자만 반환합니다.

정리

에라토스테네스의 체란?

• 소수의 배수를 제거하여 특정 범위에서 소수를 구하는 효율적인 방법.
• 작은 소수부터 시작하여 반복적으로 배수를 제거합니다.

장점

1. 효율성: O(nlog⁡log⁡n)의 시간 복잡도로 빠르게 소수를 구할 수 있습니다.
2. 단순성: 구현이 쉽고, 수학적 아이디어도 직관적입니다.

언제 사용하면 좋을까?

• 특정 범위에서 모든 소수를 구해야 할 때.
• n이 매우 큰 경우(예: 10^6 이상)에도 효율적으로 작동합니다.