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

'에라토스테네스의 체'란?

• 다수의 자연수에 대하여 소수 여부를 판별 할 때 사용하는 가장 대표적인 소수(Prime Number) 판별 알고리즘이다.


• N보다 작거나 같은 모든 소수를 찾을 때 사용 할 수 있다.

• 알고리즘의 동작 과정

  • 2부터 N까지의 모든 자연수를 나열한다.
  • 남은 수 중에서 아직 처리하지 않은 가장 작은수 i를 찾는다.
  • 남은 수 중에서 i를 제외한 i의 배수를 모두 제거한다.(i는 그 자체로 소수이기 때문에)
  • 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.
       

Python 구현

• N이하의 소수 구하기

  arr = [True] * N+1 # 리스트를 만들어 N이하의 수들을 모두 소수로 처리한다.
  arr[0], arr[1] = False  # 2부터 소수가 시작하기 때문에 0과 1은 False 처리한다.
  for i in range(2, N**(0.5)+1):  # 2부터 N의 제곱근사이의 수들 중 소수가 아닌 수가 
  있다면 N은 소수가 아니다.
      if arr[i] == True: 
      	# i는 소수이기 때문에 제외하고, i의 배수들을 False 처리한다.
          for j in range(i+i, N, i):  
              arr[j] = False
              

• 제곱근까지만 확인하면 되는 이유

  예를 들어 16이하의 소수를 구한다고 했을때, 16은 자연수 x, y 의 곱으로 표현할 수 있다.
  x, y 는 (2, 8), (4, 4)가 가능하다. 1은 소수가 아니기 때문에 제외한다.
  그리고 16 = sqrt(16) * sqrt(16)으로도 표현할 수 있다.
  그렇다면 16 = x * y or sqrt(16) * sqrt(16)으로도 표현 할 수 있다.
  즉 16의 모든 약수에 해당하는 x와 y가 어떠한 약수이더라도 둘 중 하나는 
  무조건 sqrt(16)이하이므로, sqrt*(16)까지만 조사한다면 
  16이 소수인지 아닌지 알 수 있는 것이다.
  참고 nahwasa