[알고리즘] 에라토스테네스의 체

개요 

에라토스테네스의 체는 소수를 판별하는 알고리즘입니다. 

 

이해 

* 설정 

• 2 부터 N 까지의 Boolean 배열 생성, 초기값은 True
• m^2 ≤ N 를 만족하는 자연수 중 가장 큰 m (M) 을 찾습니다. 

 

* 탐색 

• M이 1이거나 1보다 작으면 바로 탐색 종료 
• 2 ≤ i ≤ M까지 순차 탐색
  • 배열 인덱스 i 값이 True 이면
    • 배열 인덱스 i 의 배수(2배, 3배, 4배…) 값을 모두 False 로 변경
    • i 의 배수(2배, 3배, 4배…)가 N을 초과하기 전까지 반복

탐색 과정 후 배열의 값이 True 인 배열의 인덱스는 소수다. 탐색 시 i 자기 자신은 업데이트하지 않습니다. (1배수 부터가 아니라 2배수부터 값 업데이트 ) 

 

최적화 

탐색 과정에서 i의 배수를 2의 배수부터가 아니라 i의 배수부터 탐색해도 됩니다. 

 

참고 자료 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

Number Theory - 3.2 에라토스테네스의 체