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

[에라토스테네스의 체란 ?]

에라토스테네스의 체는 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘이다.

 

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.

 

에라토스테네스의 체 알고리즘의 동작 과정은 다음과 같다.

 

1. 2부터 N까지의 모든 자연수를 나열한다.

 

2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.

 

3. 남은 수 중에서 i의 배수를 모두 제거한다. (단, i는 제거하지 않는다.)

 

4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

 

 

이러한 에라토스테네스의 체를 이용해서 소수판별 프로그램을 C언어로 구현한 코드는 아래의 게시물에서 확인할 수 있다.

 

https://unie2.tistory.com/42?category=873806 

에라토스테네스의 체

 

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

1. 시간 복잡도는 사실상 선형 시간에 가까울 정도로 매우 빠르며, O(NloglogN) 이다.

 

2. 다수의 소수를 찾아야 하는 문제에서 효과적으로 사용될 수 있다.

 

   하지만, 각 자연수에 대한 소수 여부를 저장해야 하므로 메모리가 많이 필요하다.

 

 

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

import math

n = 1000 # 2부터 1,000까지의 모든 수에 대하여 소수 판별

# 처음엔 모든 수가 소수인 것으로 초기화(0과 1은 제외)
arr = [True for i in range(n+1)]

# 에라토스테네스의 체 알고리즘 수행
# 2부터 n의 제곱근까지의 모든 수를 확인
for i in range(2, int(math.sqrt(n)) + 1) :
  # i가 소수인 경우(남은 수인 경우)
  if arr[i] == True :
    # i를 제외한 i의 모든 배수를 지우기
    j = 2
    while i * j <= n :
      arr[i * j] = False
      j += 1

# 모든 소수 출력
for i in range(2, n + 1) :
  if arr[i] :
    print(i, end=' ')

 

---

출처

이것이 코딩 테스트다 with 파이썬 - 나동빈 저