에라토스테네스의 체 알고리즘 정의, 동작 방법, 성능 분석

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다.

---

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

 '다수의 자연수에 대해 소수 여부를 판별할 때' 사용하는 대표적 알고리즘.
 에라토스테네스의 체는 N보다 작거나 같은 모두 소수를 찾을 때 사용할 수 있음.

 

 에라토스테네스의 체 알고리즘의 '구체적인 동작 과정'은 다음과 같다.
  1. 2부터 N까지의 모든 자연수를 나열한다.
  2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i 를 찾는다.
  3. 남은 수 중에서 i 의 배수를 모두 제거한다. (i는 제거하지 않는다.)
  4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

 

 예) n=26 일 때, 2~26,
 1. 가장 작은 수 2를 제외한 2의 배수를 모두 제거함.
 2. 그 후 아직 처리하지 않은 가장 작은 수 3을 제외한 3의 배수는 모두 제거한다.
 3. 반복하며, 5, 7, 11, 13, 17, 19, 23... 을 처리 함.

 

import math

n=1000 
array = [True for i in range(n+1)] #2부터 1000까지 모두 배열로 처리.

for i in range(2, int(math.sqrt(n))+1):
  if array[i] == True: # i가 소수인 경우(남은 수 인 경우)
		# i를 제외한 i의 모든 배수 지우기
    j=2
    while i * j <= n:
      array[i * j] = False
      j += 1

for i in range(2, n+1):
   if array[i]:
     print(i, end=' ')

 

 

 

에라토스테네스의 체 알고리즘 성능 분석
  에라토스테네스의 체 알고리즘의 시간 복잡도는 사실상 선형 시간에 가까울 정도로 빠르다.
   -> 시간 복잡도는 O(N log logN) 이다. 백만일때, 연산 횟수는 logN=20, loglogN=4, 해서 약 4백만회
 에라토스테네스의 체 알고리즘은 다수의 소수를 찾아야 하는 문제에서 효과적으로 사용될 수  있음.
  - 하자민 각 자연수에 대한 소수 여부를 저장해야 하므로 "메모리가 많이 필요" 하다.
  - 10억이 소수인지 아닌지 판별해야 할 때 에라토스테네스의 체를 사용할 수 있을까?

 

 

---