정의

에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자인 에라토스테네스가 만들어낸 방법인데, 마치 체를 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라는 이름이 붙었다. 이 방법은 임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는, 가장 간단하고 빠른 방법이다.

방법

예를 들어 1~100까지의 숫자 중에서 소수를 찾는다고 하자.

1~100까지 숫자를 쓴다

소수도, 합성수도 아닌 유일한 자연수 1을 제거한다.

2를 제외한 2의 배수를 제거한다.

2를 남기는 이유는, 2또한 1과 자기자신으로밖에 나누어지지 않는 소수이기 때문이다. 기준이 되는 소수를 제외한 배수들부터 범위에서 제거해준다.

3을 제외한 3의 배수를 제거한다.

2를 제외할 때와 같은 이유로 3을 제외한 3의 배수부터 제거해준다.

5를 제외한 5의 배수를 제거한다.

4의 배수는 지울 필요가 없다. 2의 배수를 제거하는 과정에서 이미 지워졌기 때문이다. 따라서 2,3 다음으로 남아있는 가장 작은 소수, 즉 5를 제외한 5의 배수를 제거해야한다.

마지막으로, 7을 제외한 7의 배수까지 제거한다.

여기까지 진행하면 1~100 사이의 소수들은 모두 구할 수 있다.

왜 7까지만 진행하고, 그 다음 소수인 11은 진행하지 않는걸까?

남은 자연수 중에서 11의 1~9까지의 배수는 앞의 과정에서 모두 지워졌다. 10의 배수도 2의 배수를 지우는 과정에서 지워졌을 것이고, 그 다음 지워야할 숫자는 11의 11배를 한 수다. 그러나 11*11=121로 1~100 사이의 범위 안에 들지 않는다.

즉, 11이 100의 제곱근보다 큰 숫자이기 때문에 지울 필요가 없는 것이다. 따라서 1~N 사이의 소수를 구할 때는 N의 제곱근보다 작은 정수 M까지 범위에서 제거해주면 된다.

소스코드

아래는 에라토스테네스의 체의 코드다. 파이썬으로 작성했다.

import math

MAX = 100
prime = [True for i in range(MAX+1)]

prime[1] = False

for i in range(2, int(math.sqrt(MAX))+1):
	if prime[i] == True:
    	j = 2
        while i*j <= MAX:
        	prime[i*j] = False
            j += 1
    
for i in range(2, number):
    if(prime[i]): print(i)	

작성하면서 헷갈렸던 부분이 많아서 자세하게 더 정리해봤다.

선언

import math

MAX = 100
prime = [True for i in rnage(MAX+1)

우선은 제곱근을 구하려면 sqrt() 함수를 사용해야 하기 때문에 import math를 해준다. 그러고 범위를 지정해주기 위해 최댓값을 MAX에 선언해주고, MATH+1 한 만큼의 크기를 배열로 만들어준다. 배열은 모두 True로 채워준다.

체로 거르기

prime[1] = False

for i in range(2, int(math.sqrt(MAX))+1):
	if prime[i] == True:
    	j = 2
        while i*j <= MAX:
        	prime[i*j] = False
            j += 1

우선 소수도, 합성수도 아닌 1을 먼저 제외해주고 시작한다.

그런 다음 앞에서 2,3,5,7의 배수를 제거해주는 과정을 진행할 것이다. 제거해주는 숫자는 MAX의 제곱근을 넘으면 안되기 때문에 sqrt() 함수를 통해 범위를 정해준다.

while 문을 통해서 prime 안의 값을 False로 바꿔주는 과정을 진행하는데, 제거해주는 숫자인 i의 2배수 부터 진행해야 하기 때문에 j는 2로 선언해준다. 그 다음 while문을 돌면서 1씩 증가시켜주다가 i와 j를 곱한 값이 MAX보다 커지는 순간 while문을 종료해준다.

이 과정을 진행하면 prime 배열에는 True와 False만이 담기게 된다. prime[i]를 이용해서 살펴볼 때, i가 소수인 칸에는 True, 소수가 아닌 칸에는 False가 담겨있다. 1부터 MAX까지 숫자를 담지 않은 이유는 그렇게 할 경우 메모리가 차지하는 크기가 커지기 때문이다. True와 False만을 사용할 때 상대적으로 에라토스테네스의 체를 가볍게 만들 수 있다.

출력하기

for i in range(2, number):
    if(prime[i]): print(i)	

그런 다음, prime[i]가 True일 때의 i를 출력하면 범위내의 소수들을 출력할 수 있다.