[알고리즘] 에라토스테네스의 체

에라토스테네스의 체 동작 원리

Introduction
아래 그림과 같이 N 이하의 모든 소수를 찾으려면 2부터 시작해서 모든 숫자의 배수들을 제외하면 된다. 어떤 숫자의 배수라는 것은 합성수이고 소수가 아니라는 의미이기 때문이다. 이 때, 배수를 제외하는 연산은 생각보다 많지 않다. 어차피 작은 숫자부터 시작해서 배수를 지우면 뒤로 갈수록 앞에서 이미 많이 걸러져서 제외할 숫자가 많이 남아있지 않기 때문이다.

 

출처: 위키백과

N 이하의 모든 소수를 에라토스테네스의 체로 걸러서 구하는 순서

 

1. 사이즈 N 의 배열에 2부터 시작해서 이하의 소수를 모두 구하고 싶은 숫자까지를 모두 넣는다. 주의할 점은 모두 숫자와 일치하는 인덱스에 넣어야 한다는 것이다. (2는 배열의 인덱스 2, 3은 배열의 인덱스 3, .... N 은 배열의 인덱스 N)

Hint
0 과 1은 소수가 아니므로 배열이 생성될 때의 기본값인 0에서 변하지 않는 것이 맞다.

 

2. 최소 소수인 2부터 현재 숫자의 제곱근까지 확인하면서 배수 찾기를 시작한다.

Hint
제곱근까지 찾는 이유는 어차피 그 이후 숫자들 중 합성수들은 모두 이미 그 전에 배수로 걸러지기 때문이다.
예를 들어, 50의 제곱근은 7이다. 7까지는 7 * 7 (49) 부터 시작해도 배수를 처음 찾는 것이라 무리가 없지만, 이후의 숫자들은 어차피 8 * 6 을 해도 이미 했고, (6  * 8 에서)  8 * 5를 해도 이미 했다. (5 * 8 에서) 배수를 찾는 것이 의미가 있는 최소 시작 시점이 8 * 8 인데 이미 56 으로 50 을 넘어가서 해볼 필요가 없다.

 

3. i 의 제곱이 N 보다 작거나 같을 때는 nested for 문이 작동한다. nested for 문에서는 i 의 제곱부터 시작해서 i 를 더해가면서 0을 할당한다. 즉, 배수 찾기가 실제로 이루어지는 곳이 여기이다.

 

4. 이중 포문을 다 돌고 나면, 0이 배정되어 있지 않은 숫자들은 모두 소수이다. 배열에서 확인하면 된다.

Java 로 구현하기

이제 Java 에서 에라토스테네스의 체를 간단하게 구현해본다. 아래는 위의 설명대로 구현한 코드이다.

    public int[] findPrimes(int num) {
        int[] primes = new int[num+1];

        for (int i = 2; i <= num; i++) {
            primes[i] = i; // 2부터 숫자까지의 모든 수를 배열에 넣는다.
        }

        for (int j = 2; j * j <= num; j++) {
			
            // 이미 0이 배정된 수의 배수는 알아보지 않아도 된다.
            // 어차피 이 숫자의 모든 배수는 나누어지는 수가 하나는 있다는 뜻이기 때문이다.
            if (primes[j] == 0) continue;
			
            // 제곱부터 알아본다. j * j - 1 까지의 숫자들은 모두 이전에
            // j - n (n은 1 이상이다) * j 연산으로 배수 찾기가 완료되었다.
            for (int k = j * j; k <= num ; k += j) {
                primes[k] = 0;
            }
        }
		
        // 이제 소수인 수만 남고 나머지 수들은 0으로 치환되었다.
        // 0을 제외한 수들을 리스트에 넣자.
        List<Integer> primeNums = new ArrayList<>();
        for (int l = 2; l < primes.length; l++) {
            if (primes[l] == 0) continue;
            primeNums.add(primes[l]);
        }
		
        // 리스트를 배열로 바꿔서 반환한다.
        return primeNums.stream().mapToInt(i->i).toArray();
    }

출처

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

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전