에라토스테네스의 체
에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 개발한 소수를 찾는
효율적인 알고리즘이다. 에라토스테네스의 체는 주어진 수 n 이하의 모든 소수를 찾기 위해 소수가 아닌 수를 체로 걸러내듯이 제거하는 방식으로 동작한다. 즉, 소수의 배수를 차례로 지워나가면 남는 수가 소수
가 된다. 해당 알고리즘을 통해 소수를 매우 효율적이게 구할 수 있다.
에라토스테네스의 체 원리
우선 숫자 15 까지의 숫자 중 소수를 찾아야한다면 (15 + 1) 크기의 배열을 1로 초기화시켜준다.
+ 1 를 해주는 이유
배열은 index 가 0 부터 시작하기 때문이다. 따라서 index 가 15 까지 있게 하려면 0 을 포함한 배열의 크기는 16 이 된다.
소수는 2부터 시작하기 때문에 순회를 number = 2 부터 시작한다. 그리고 자기 자신(소수 2) 를 제외한 소수의 배수(2,4,6,8,10,12) 를 0 으로 바꾸어 준다.
마찬가지로 number = 3 일때도 마찬가지이다.
이렇게 15 까지의 수들 중 소수를 찾는 과정은 여기서 마무리 된다.
Note
4 와 그 배수는 소수 2 의 배수 에서 이미 지웠졌다.
왜 일부만 돌까?
여기서 의문이 들 수 있는 것은 “왜 15 까지 모두 순회를 하지 않냐” 이다. 결론부터 말하면 15 의 제곱근인 3.87, 즉 3 이하까지만 순회하면 되고, 4 이상은 확인할 필요가 없다. 그 이유는 소수의 배수를 지울 때 그 이상의 수는 이미 지워졌기 때문
이다. 좀 더 정확한 이유는 아래와 같다.
- 2의 배수를 모두 지우면 남는 숫자 중 2의 배수는 없기 때문.
- 3의 배수를 모두 지우면 남는 숫자 중 3의 배수는 없기 때문.
- 4는 이미 2의 배수에서 지워졌고, 5는 소수이므로 지우지 않는 것.
Python 코드
이 과정을 Python 코드로 표현하면 아래와 같다.
시간복잡도
전체 알고리즘의 시간 복잡도는 O(nloglogn)
단점
메모리 사용량
- 에라토스테네스의 체는 n 크기의 배열을 사용한다. 따라서 n 이 매우 클 경우, 메모리 사용량이 많아진다. 예를 들어, n 이 10^9와 같은 큰 숫자일 경우, 배열의 크기가 매우 커지므로 메모리가 부족할 수 있다.