에라토스테네스의 체를 이용한 소수 판별 (Python)

개념

에라토스테네스의 체는 구간에서 여러 개의 수가 소수인지 아닌지를 판단할 때 유용한 알고리즘입니다. 에라토스테네스의 체를 사용하기에 앞서 소수의 성질을 살펴보겠습니다.

1부터 10까지의 숫자가 있을때 즉 다음과 같을 때 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. 소수는 1을 제외한 수들 중 약수가 자기 자신과 1만 존재하는 수입니다. 따라서 2, 3, 5, 7이 소수입니다. 

 

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

 

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

2. 숫자들 중 아직 처리하지 않은 수를 찾는다.

3. 그 숫자의 배수들을 제거한다. 단 2 배수부터 제거한다. (2나 3이 제거되는 것을 방지)

4. 위의 2, 3,  과정을 반복한다.

---

소스코드

 

import math
# 1부터 100까지의 소수를 모두 찾는 에라토스테네스의 체
n = 100
array = [True] * (1 + n)
 
for i in range(2, int(math.sqrt(n) + 1)):
  if array[i] == True: # 아직 처리되지 않은 숫자인 경우
    j = 2
    while i * j <= n:
      array[i * j] = False
      j += 1
 
for i in range(2, n+1):
  if array[i] == True:
    print(i, end=" ")