[java] 소수 구하기(에라토스테네스의 체)

에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 고안한 소수(Prime Number)를 빠르게 구하는 알고리즘이다.

특정 수 N 이하의 모든 소수를 구할 때 매우 효율적이다.

이 알고리즘의 시간 복잡도는 O(Nlog(logN))이다.

핵심 아이디어
- 2부터 시작해서, 아직 지워지지 않은 가장 작은 수를 소수로 기록한다.
- 그 수의 배수들은 모두 지운다.
- 이를 N까지 반복한다.

 

1. 크기가 N + 1인 배열을 선언한 후 인덱스 0과 1은 false 처리한다.

N이 16이라고 가정하면 배열은 아래와 같다.

 

2. 인덱스 2부터 시작해서 N의 제곱근(=4)까지 해당 인덱스의 배수를 순차적으로 탐색한다. 값이 true라면 false로 바꿔준다.

N의 제곱근까지만 탐색하는 이유
어떤 수 N이 두 수 a와 b의 곱이라고 할 때, a와 b가 둘 다 √N보다 크면 곱했을 때 N을 넘기게 되므로, 적어도 하나는 √N보다 작거나 같다.
예를 들어 16은 4×4인데, 이보다 작은 곱을 만들려면 반드시 하나는 4 이하여야 한다.
그래서 소수인지 판별할 때 √N까지만 확인해도 모든 경우를 다 검사한 것이나 마찬가지다.

 

3. 앞의 과정을 배열의 끝까지 반복한다.

 

이를 코드로 나타내면 아래와 같다.

import java.util.Arrays;

public class Eratosthenes {
    public static boolean[] sieve(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true); // 처음엔 전부 소수(true)로 가정
        isPrime[0] = false;
        isPrime[1] = false;

        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false; // i의 배수 제거
                }
            }
        }
        return isPrime;
    }

    public static void main(String[] args) {
        int n = 50; // 50까지의 소수를 구함
        boolean[] primes = sieve(n);

        for (int i = 2; i <= n; i++) {
            if (primes[i]) {
                System.out.print(i + " ");
            }
        }
    }
}