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

개념

 

에라토스테네스의 체는 구간에서 여러 개의 소수가 소수인지 아닌지 판별하는 알고리즘입니다.

 

소수란?

 

1과 자기자신만을 약수로 가지는 수 입니다.

ex) 1 ~ 10 까지의 수 중에서 소수는 2,3,5,7 입니다 (1과 자기자신만을 약수로 가짐)

 

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

 

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=" ")