파이썬(Python) - 에라토스테네스의 체 : 범위 내 존재하는 모든 소수 찾기 알고리즘

이전 글에서 소수를 찾는 효율적인 방법을 알아보았다.

파이썬(Python) - 소수 찾기 알고리즘 구현하기(Prime Number)

위의 방법을 사용하면 확인하고자 하는 숫자가 소수인지는 파악하는 것은 문제가 없지만,

일정 범위 내에 존재하는 모든 숫자 중에서 소수를 모두 찾으려면 굉장히 오랜시간이 걸리게된다.

모든 숫자를 하나씩 검사해봐야하기 때문이다.

따라서 전혀 다른 방식의 알고리즘을 사용해야하는데 이럴 때 사용할 수 있는 알고리즘이 바로 '에라토스테네스의 체'이다.

 

---

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

 

해당 알고리즘은 N보다 작거나 같은 모든 소수를 찾을 때 쓸 수 있다.

방식은 다음과 같다.

 

1. 2부터 N까지 존재하는 모든 자연수를 나열한다.

2. 나열된 숫자 중에서 가장 작은 수를 x로 지정한다.

3. 나열된 숫자 중에서 x의 배수를 모두 제거한다. (이때, x는 제거하지 않는다)

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

 

이 모든 과정이 끝났을 때까지 남아있는 숫자들이 소수인 숫자들이다.

 

그리고 이 과정을 코드로 작성하면 다음과 같다.

import math

n = 1000	# 2부터 1000까지 모든 수에 대하여 소수를 찾을 것이다.
array = [True for i in range(n + 1) # 0,1을 제외한 모든 숫자가 소수(True)인 것으로 설정하고 시작한다.

# 에라토스테네스의 체 알고리즘
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 range(2, n + 1):
	if array[i]:
    	print(i, end = ' ')

 

이 알고리즘은 생각보다 속도가 매우 빠르다.

따라서 다수의 소수를 찾는 문제를 굉장히 빠르게 해결할 수 있지만,

N의 크기만큼 리스트를 만들어서 할당해야하기 때문에 굉장히 많은 메모리를 필요로하는 단점이 있다.

대략 십억이 넘어가는 크기의 숫자가 되면 해당 알고리즘 말고 다른 알고리즘을 생각해봐야한다.