Skip to main content

에라토스테네스의 체

개요​

소수를 판별하는 알고리즘

알고리즘​

설정​

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

참고 자료​