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

📌 본 내용은 '이것이 취업을 위한 코딩 테스트다 with 파이썬(나동빈 지음)'을 참고하여 작성하였습니다.

 

에라토스테네스의 체

N 보다 작거나 같은 모든 소수를 찾을 때 사용하는 대표적인 알고리즘

 

소수 판별 과정

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

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

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

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

 

소수 판별 프로그램

import math

n = 10 # 2부터, 10까지의 모든 수에 대하여 소수 판별
array = [True for i range(n + 1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)
# array[1] = False

# 에라토스테네스의 체 알고리즘
for i in range(2, int(math.sqrt(n) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
	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=' ')

2 3 5 7

 

❗ 주의해야할  점

• 문제에서 1이 소수인지 판별해야 하도록 입력 조건이 주어진 경우  array[1] = False 추가
• 알고리즘을 수행할 때 N의 크기만큼 리스트를 할당해야 하므로 메모리가 많이 필요 N이 1,000,000 이내로 주어지는 경우 사용