에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견한 것으로 마치 체로 숫자를 걸러내는 것처럼 보여 '에라토스테네스의 체' 라고 불린다.
먼저 소수란, 1보다 큰 자연수 중 1과 자기자신만을 약수로 가지는 수이다. 예를 들어 2, 3, 5, 7은 약수인데 이들은 모두 1과 자기자신으로만 나누어질 수 있다. 반면에 4는 1과 자기자신 4 말고도 2로 나누어지기 때문에 소수가 아니다.
'에라토스테네스의 체'의 원리에 대해서 알아보자.
알고리즘 설명
1부터 120까지의 숫자중 소수를 찾아보자.
1) 1부터 소수를 구하고자하는 구간인 120까지 나열한다.
2) 먼저 1을 제거한다.
3) 2는 소수이므로 Prime Numbers에 기입
4) 자기자신을 제외한 2의 배수를 모두 지운다.
5) 3도 소수이므로 Prime Numbers에 기입
6) 자기자신을 제외한 3의 배수를 모두 지운다.
7) 지워지지 않은 다음 수인 5도 소수이므로 Prime Numbers에 기입
8) 자기자신을 제외한 5의 배수를 모두 지운다.
9) 위 두개의 과정 반복하여 소수를 구한다.
120까지의 구간에서 보았을 때 11의 제곱은 120보다 크므로 11보다 작은 수의 배수들만 지워도 충분하다.
알고리즘 구현 (파이썬)
def prime_list(n):
sieve = [True] * (n + 1) # n개 구간의 모든 수 True로 초기화(소수로 간주)
m = int(n ** 0.5) # n의 최대 약수가 sqrt(n)이므로 i가 sqrt(n)까지 확인
for i in range(2, m + 1):
if sieve[i] == True: # i가 소수인 경우
for j in range(i * 2, n, i): # i이후 i의 배수를 모두 False 처리
sieve[j] = False
# 소수 목록 return
return [i for i in range(2, n) if sieve[i] == True]
[참고]
에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소수를 구하고자 하는 구간
ko.wikipedia.org
댓글