Sieve of Eratosthenes, 에라토스테네스의 체

에라토스테네스의 체Sieve of Eratosthenes는 2부터 n까지의 숫자 중 모든 소수prime number를  찾기 위한 간단한 알고리즘이다.

1. 오름차순으로 2 부터 n까지의 모든 숫자를 set={ 2, 3, ..., n} 집합에 갖고있다.

2. 아직 처리하지 않은 숫자 중 가장 작은 숫자를 선택한다.

3. 해당 숫자의 배수들을 집합에서 모두 지운다. 

4. 2로 돌아간다. 

끝. 위의 방법으로 모든 합성수들을 집합에서 지울 수 있다. 하지만 2-4번을 N번 반복하는 코드를 작성한다면 O(n**2)시간이 걸릴 것이다. 

O(n log log n) 시간 걸리는 코드를 작성하기 위해서는 합성수composite number를 제거하는 동작의 중복을 줄이면된다.

- 모든 합성수composite number 는 최대 √n개의 약수를 갖는다. √: 제곱근

- 각 숫자의 배수multiple를 집합에서 지울때, 그 숫자의 제곱수에서부터 제거하기 시작해도  충분히 소수만 남기는 작업을 수행할 수 있다.

위키피디아 이미지

에라토스테네스 체 알고리즘을 사용하여 N 이하의 소수를 프린트하는 python3 코드이다.

직접 작성한 에라토스테네스 체 코드가 잘 돌아가는지 Geeks for geeks  페이지에서 확인해볼 수 있다.