에라토스테네스의 체

에라토스테네스의 체 (Sieve of Eratosthenes) 는 주어진 범위 내에서 소수를 구하는 알고리즘입니다. 이 방법은 모든 자연수 중에서 소수만을 찾아내는 알고리즘으로, 시간 복잡도가 `O(n log(log n))`으로 매우 효율적입니다. 기본 아이디어는 2부터 시작하여 각 숫자의 배수를 모두 지워 나가는 방식입니다.

에라토스테네스의 체 개념:
1. 배수 지우기: 2부터 시작하여, 2의 배수들(4, 6, 8, ...)을 모두 지웁니다. 그다음 3의 배수들(6, 9, 12, ...)을 지우고, 4는 이미 지워졌으므로 5의 배수들(10, 15, 20, ...)을 지웁니다. 이런 식으로 숫자를 지워 나갑니다.
2. 남은 숫자들: 마지막에 남은 숫자들은 모두 소수입니다.

에라토스테네스의 체 알고리즘의 핵심:
- `i`가 소수라면, 그 배수들(`ii, ii + i, ...`)은 모두 소수가 아니므로 지웁니다.
- 이 과정을 `i`가 `sqrt(n)` 이하일 때까지 반복하면 됩니다. 왜냐하면 그 이후의 배수는 이미 이전 단계에서 지워지기 때문입니다.

자바로 구현한 예시:

private boolean isPrime(int num) {
    if (num <= 1) {
        return false;
    }
        
    for (int i = 2; i <= Math.sqrt(num); i++) {	
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

에라토스테네스의 체가 효율적인 이유:
- 배수 지우기 방식은 중복되는 작업을 최소화하여, 각 숫자의 배수만 한 번씩 처리됩니다.
- 따라서 시간 복잡도가 `O(n log(log n))`으로 매우 효율적입니다. 이를 통해 큰 범위의 소수를 빠르게 구할 수 있습니다.

요약:
- 에라토스테네스의 체는 2부터 `n`까지의 수 중 소수인 수를 빠르게 구할 수 있는 알고리즘입니다. 소수 판별을 할 때 배수를 하나씩 지워나가는 방식으로, 이를 통해 소수를 효율적으로 찾아낼 수 있습니다.