에라토스테네스의 체

개요

소수를 판별하는 알고리즘

알고리즘

설정

• 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의 배수부터 탐색해도 된다.

참고 자료

• https://ko.wikipedia.org/wiki/에라토스테네스의_체
• https://ps.mjstudio.net/number-theory-3-2