정수론 : 소수 구하기 에라토스테네스의 채

소수

소수 구하기의 핵심 이론

소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체를 들 수 있다. 에라토스테네스의 체 원리는 다음과 같다.

① 구하고자 하는 소수의 범위만큼 1차원 리스트를 생성한다.
② 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우 현재 선택된 숫자의 배수에 해당하는 수를 리스트에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.
③ 리스트의 끝까지 ②를 반복한 후 리스트에서 남아 있는 모든 수를 출력한다.

에라토스테네스의 체를 사용할 때 시간 복잡도

일반적으로 에라토스테네스의 체를 구현하려면 이중 for문을 이용하므로 시간 복잡도가 O(N^2) 정도라고 판단할 수 있다. 하지만 실제 시간 복잡도는 최적화의 정도에 따라 다르겠지만, 일반적으로 O(Nlog(logN))이다. 그 이유는 배수를 삭제하는 연산으로 실제 구현에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문이다. 이러한 이유 때문에 에라토스테네스의 체 기법은 현재에도 코딩 테스트에서 소수를 구하는 일반적인 방법으로 통용되고 있다.

 

관련 문제

 

백준

1929	소수 구하기	성공	55737	269080	27.457%
1456	거의 소수		2393	13957	24.002%
1747	소수&팰린드롬		6486	27114	30.501%
1016	제곱 ㄴㄴ 수		8445	61807	21.765%

 

 

책 <Do It! 알고리즘 코딩테스트>_김종관 지음, 이지스퍼블리싱 출판사

학교 알고리즘 수업 강의자료 등 여러 자료 참고해서 공부함.