Algorithm - 에라토스테네스의 체

에라토스테네스의 체는 2부터 원하는 숫자까지의 소수를 판별하는 방법이다. 소수를 판별하는 방법은 다음과 같다.

1. 이전 소수에 의해 지워지지 않았다면, 이 숫자는 소수이다.
2. 체로 인해 소수로 걸러졌다면, 구간에서 이 소수의 배수를 모두 지워준다. 구간의 끝까지 이를 반복한다.

이해를 돕기 위해 예시를 들어 설명한다면, 예를 들어 31까지 소수를 구별한다고 하자.

2	3	4	5	6
7	8	9	10	11
12	13	14	15	16
17	18	19	20	21
22	23	24	25	26
27	28	29	30	31

2부터 시작한다.

2는 이전 소수에 의해 지워지지 않았으므로 소수이며, 이 구간에서 2의 배수를 모두 지워준다.

2	3		5
7		9		11
	13		15
17		19		21
	23		25
27		29		31

다음으로 3은 이전 소수에 의해 지워지지 않았으므로 소수이며, 이 구간에서 3의 배수를 모두 지워준다.

2	3		5
7				11
	13
17		19
	23		25
		29		31

다음은 5이다.

5는 이전 소수에 의해 지워지지 않았으므로 소수이며, 이 구간에서 5의 배수를 모두 지워준다.

이런식으로 31까지 반복하면 이 구간에서 소수를 모두 거를 수 있다.

2	3		5
7				11
	13
17		19
	23
		29		31

추가로 5 이후 부터는 31의 제곱근보다 크기 때문에 이미 소수가 아닌 수들은 지워져있으므로 본 예시에서는 5까지만 과정을 반복하면 된다.

이를 적용한 파이썬의 소스코드이다.

from math import sqrt
def sieve_of_eratosthenes(x):
    arr = [True] * x
    for i in range(2, int(sqrt(x))+1):
        if arr[i]:
            for j in range(i+i, x, i):
                arr[j] = False