에라토스테네스의 체 [Kotlin] with 백준 2851

에라토스테네스의 체란

고대 그리스 수학자 에라토스테네스가 만들어낸 대표적인 소수 판별 알고리즘입니다. 

 

아래에서 더욱 자세히 설명될 것이다.

소수

소수란 나눠지는 수가 1과 자기 자신밖에 없는 수를 뜻한다.

 

알고리즘

에라토스테네스의 체란 구하고자하는 모든 수를 나열한 이후 각 소수의 제곱수와 배수들을 하나씩 없애나가는 것이다.

 

조금 더 자세히 설명하자면 

1. 구하려는 모든 수들을 나열한다. 회색으로 칠해진 수들이 그 수들이다.

2. 2는 소수이므로 오른쪽에 2를 쓴다.

3. 자기 자신을 제외한 2의 배수들을 모두 지운다. (빨간색)

4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. 

5. 자기 자신을 제외한 3의 배수들을 모두 지운다. (초록색)

6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.

7. 자기 자신을 제외한 5의 배수들을 모두 지운다. (파란색)

8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다.

9. 자기 자신을 제외한 7의 배수들을 모두 지운다. (노란색)

10. 위의 과정을 거치면 소수가 나온다.

 

7까지만 해주는 이유는??

다음 소수는 11인데 11의 제곱은 121이다.

예시가 120까지이니 11부터는 해줄 필요가 없다.

소수의 제곱수까지만 해주면 되는 이유는 무엇일까 

만약에 제곱수를해주지 않고 배수를 해주게 된다면

11 * 2, 11 * 3, 11 * 4 ∙∙∙ 으로 진행될텐데

사실 이걸 돌려본다면 2 * 11로 이미 2의 배수에서 지워졌을 것이고,

3 * 11또한 마찬가지이다.

4 * 11과 같이 소수가 아닌수들은 이미 더욱 작은 수들을 반복할 때 지워진 숫자들이다.

 

따라서 11을 기준으로 본다면 

11보다 작은 2, 3, 4, 5, 6, 7, 8, 9, 10 과 곱해지는 모든 수들이 이미 다 지워진 숫자들이다. 

따라서 해당 소수의 제곱수부터 소수를 점점 더하는 방식으로 진행된다.

 

Kotlin 으로 구현된 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val min = readLine().toInt()
    val max = readLine().toInt()

    // 초기 값들을 모두 소수라고 판단하고 구하려는 수 + 1 사이즈만큼 array 생성
    val isPrime = Array(max + 1) { true }
    isPrime[0] = false
    isPrime[1] = false

    val arr = mutableListOf<Int>()

    // 소수 판별 알고리즘
    for(i in 2..max) {
        // 만약 해당 값이 소수라면 진행
        if(isPrime[i]) {
            // 해당 소수의 제곱부터 시작하여 + i를 max 까지 진행
            for(j in (i * i).. max step i) {
                isPrime[j] = false
            }
        }
    }
    isPrime.forEachIndexed { index, b ->
        if(index >= min && b) arr.add(index)
    }
    if(arr.size > 0) {
        println(arr.sumOf { it })
        println(arr.first())
    } else
        println(-1)
}

 

해당 코드는 에라토스테네스의 체를 살짝 응용하여

백준 2581번 소수 문제를 코틀린으로 풀었던 코드이다. 

 

 

해당 포스트는 위키백과를 참고하여 제작되었습니다.