소수 구하기: 에라토스테네스의 체

#자료구조/알고리즘

일단 여기서 말하는 소수(Prime Number)는 1과 자신 이외의 수로 나눌 수 없는 수를 말한다.

특점 범위의 시퀀스에서 소수들만을 찾아내려면 어떻게 해야할까?

무식하게 구현한다면 대충 이런식으로 구현할 수 있을 것이다.

그냥 하나하나 순회하면서 다 소수임을 검증했다.

근데 소수 검증 작업 자체가 상당히 비싸기 때문에

대략 N*√N의 복잡도를 가진다. 싸다고 하기는 힘들다.

에라토스테네스의 체
그 유명한 고대 그리스인 에라토스테네스가 고안한 방법론이다.
그 방법은... 이 이미지를 보는게 이해가 빠를 것이다. 위키피디아에서 가져왔다.

일단 검증할 목록을 전부 할당해놓은다음에, 2의 배수, 3의 배수 순으로 소수가 아닌 것들을 지워버리는 기법이다.
체로 걸러내듯이 말이다.

처음의 구현처럼 무식하게 다 도는게 아니기 때문에, 대강 O(N * (log log N))의 복잡도를 가진다고 한다.

짜서 성능을 비교해봤는데, 역시 차이가 확연하다.실행환경은 Visual Studio 2019, x86 릴리즈모드다.

저대로 돌려보면

케이스가 커질수록 성능의 차가 확연히 벌어짐을 알 수 있다.
이외에도 다른 체들이 몇가지 있지만, 일단은 이것으로 마치도록 한다.
사실 이것만 해도 충분한 효율성을 가진다. 고만고만하다.