[알고리즘] 에라토스테네스의 체 (Sieve of Eratosthenes)

 

 

 

 

에라토스테네스의 체. 이름이 조금 어려운 알고리즘입니다.

에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 고안한

소수(Prime Number)를 찾는 알고리즘 중 하나인데요.

 

일반적으로 정수 n이 소수인지 확인할 때,

for문을 돌리며 2~sqrt(n)으로 나누어 떨어지나 확인하는 방법이 있습니다.

 

하지만 특정 범위 내 여러 개의 수를 소수인지 판단해야 할 때,

각각 2~sqrt(n)으로 나누어 떨어지는지 확인하는 것은 조금 비효율적일 수 있습니다.

 

하지만, 처음에 범위 내 숫자들에 대해 소수인지 구해놓고

이후에 각 숫자들이 소수인지 확인한다면 더 빠르게 작동할 수 있습니다.

 

 

 

에라토스테네스의 체

 

출저 : 위키피디아 https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

 

에라토스테네스의 체의 원리를 그림으로 표현하자면 위 이미지와 같습니다.

2 ~ 120 범위 내 숫자들에 대해 소수를 구해봅시다.

1) 소수 2의 배수인 4, 6, 8, 10 ... 118, 120을 모두 지운다.

2) 그 다음 소수 3의 배수인 6, 9, 12, 15, 18, ... , 117, 120을 지운다.

3) 4의 경우 이미 지웠으므로 넘어간다.

4) 그 다음 소수 5의 배수인 10, 15, 20, 25, 30, 35.. 115, 120을 지운다.

5) 6은 이미 지웠으므로 넘어간다.

6) 그 다음 소수 7의 배수인 14, 21, 28, 35...112, 119를 지운다

 

위 과정을 sqrt(120)까지 반복하여

다시 처음으로 돌아와 지워지지 않은 숫자만 뽑으면

2, 3, 5, 7, 11 ... 등 소수만 뽑아낼 수 있습니다.

 

마치 체로 소수를 걸러내는듯 하여 붙은 이름이죠.

 

 

 

소스코드로 구현

Java

public class Main {
    public static void main(String[] args) {
        int n = 120;
        boolean[] isPrime = new boolean[n + 1];

        // 모든 수를 소수로 초기화
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }

        // 에라토스테네스의 체
        for (int i = 2; i * i <= n; i++) {

            // i가 소수인 경우
            if (isPrime[i]) {

                // i의 배수를 모두 지우기
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // 소수 출력
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                System.out.println(i);
            }
        }
    }
}

=============================================
// 출력
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113

 

 

 

Kotlin

fun main() {
    val n = 120
    val isPrime = BooleanArray(n + 1) { true }

    // 모든 수를 소수로 초기화
    for (i in 2..n) {
        isPrime[i] = true
    }

    // 에라토스테네스의 체
    for (i in 2..(Math.sqrt(n.toDouble())).toInt()) {

        // i가 소수인 경우
        if (isPrime[i]) {

            // i의 배수를 모두 지우기
            var j = i * i
            while (j <= n) {
                isPrime[j] = false
                j += i
            }
        }
    }

    // 소수 출력
    for (i in 2..n) {
        if (isPrime[i]) {
            println(i)
        }
    }
}

 

 

 

 

후기

특정 범위 내 소수를 찾는데 특화된 알고리즘인 에라토스테네스의 체 입니다.

다소 노가다식 방법이지만 아래 문제와 같이 특정 범위 내 여러 소수를 찾아야 할 때 유용한 알고리즘입니다.

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

 

다만 하나의 수만 주어지고, 이 수가 소수인지 확인하는 것이라면

에라토스테네스의 체 보다 빠른 다른 소수 찾기 알고리즘을 사용하는 것이 좋습니다.