[Tech, Algo] Sieve of Eratosthenes (에라토스테네스의 체)

에라토스테네스의 체는 소수를 찾아내기 위한 알고리즘으로, 교과 과정에서도 배우는 내용 중 하나다. 이 알고리즘은 LeetCode 204. Count Primes 와 같은 인터뷰에도 종종 등장하므로 알고 있으면 매우 유용하다.

 

고대 그리스 수학자 에라토스테네스가 발견한 이 알고리즘은 '체'로 치듯이 수를 걸러낸다고 해 '에라토스테네스의 체'로 불린다. 이 알고리즘의 포인트는 배수와 제곱근을 활용하는 것이다. 예를 통해 이해해보자.

 

1. 1부터 100까지의 숫자 중 소수를 찾는다 가정하자.
2. 1부터 100까지의 숫자를 나열해보자.
3. 작은 숫자부터 시작을 하고, 특수한 경우인 1을 우선 지운다.
4. 2를 제외한 2의 배수를 지운다. (배수 활용 시작)
5. 3을 제외한 3의 배수를 지운다.
6. 4의 배수는 이미 2의 배수를 통해 지웠으므로, 다음 숫자로 넘어가자.
7. 5를 제외한 5의 배수를 지우고, 6의 배수는 2와 3을 통해 지워졌으므로 7로 넘어가자.
8. 같은 방식으로 10까지만 확인하면, 11부터는 확인이 불필요하다. 11의 배수는 이미 11에 2부터 9까지 곱한 경우 (22, 33, ..., 99) 에 대해 지워졌기 때문이다. (제곱근 활용)

아래는 이에 대한 Python 구현이다. 참고로 시간 복잡도는 O (n log log n) 이다.

import math
class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 1:
            return 0
        isPrime = [1] * n
        isPrime[0], isPrime[1] = 0, 0
        for i in range(int(math.sqrt(n)) + 1):
            if isPrime[i]:
                cur = i * 2
                while cur < n:
                    isPrime[cur] = 0
                    cur += i
        return sum(isPrime)

 

참고

- https://leetcode.com/problems/count-primes

- https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

- 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