에라토스테네스의 체(Sieve of Eratosthenes)

고대 그리스 수학자 에라토스테네스가 만들어낸 소수 찾는 방법.

이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.

임의의 자연수 N에 대해, 그 이하의 소수를 모두 찾는 방법이다.

 

방법

자기 자신을 제외한, 자신의 배수를 지워나가면 된다.

아래 예시(N = 30)를 통해 확인해보자.

1	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

 

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

1	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

 

2를 제외한, 2의 배수를 지운다

1	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

 

3을 제외한, 3의 배수를 지운다

1	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

 

4의 배수는 지울 필요가 없다. (2의 배수에서 지워졌다)

5를 제외한, 5의 배수를 지운다.

1	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

 

6의 배수는 지울 필요가 없다. (2의 배수에서 지워졌다)

7을 제외한, 7의 배수를 지운다.

1	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

 

8의 배수는 지울 필요가 없다. (2의 배수에서 지워졌다)

9의 배수는 지울 필요가 없다.. (3의 배수에서 지워졌다)

10의 배수는 지울 필요가 없다. (2의 배수에서 지워졌다)

11을 제외한, 11의 배수를 지운다. (22는 이미 지워졌으므로, 남아있는 수정에서 삭제되는 값은 없다)

13을 제외한, 13의 배수를 지운다. (26는 이미 지워졌으므로, 남아있는 수정에서 삭제되는 값은 없다)

14의 배수는 지울 필요가 없다. (2의 배수에서 지워졌다)

15의 배수는 지울 필요가 없다.. (3의 배수에서 지워졌다)

16의 배수는 N(30)보다 크다. 따라서 여기까지만 진행한다.

지워지지 않고, 남아있는 수들이 소수이다.

 

최적화

위의 예제에서 N = 30 일 때, 16의 배수까지 알아보았다.

사실 좀 더 일찍 끝낼 수 있다.

결론부터 얘기하면 \( \sqrt{N} \) 이하의 수의 배수만 지우면 된다.

 

증명

N이 합성수라면, N은 다음과 같이 표현할 수 있다.

\( N = A \times B \)

\( N = A \times \frac{N}{A} \)

여기서 A는 \( A \leq \frac{N}{A} \) 이므로, \( A \leq \sqrt{N} \)로 정리할 수 있다.

따라서 합성수 N은 \( \sqrt{N} \)보다 작거나 같은  최소 소인수(A)를 갖는다.

 

이번에는 N보다 작은, 합성수 M을 생각해보자. 

합성수 M은 M = CD로 표현할 수 있고,

위와 같은 논리로 C와 D 중 적어도 하나는 \( \sqrt{M} \) 이하이다.

또한, M < N 이므로, \( \sqrt{M} < \sqrt{N} \) 이다.

즉, N보다 작은 합성수 M은 \( \sqrt{N} \) 보다 작은 수의 배수만 확인해도 전부 지워진다는 의미이다.

따라서 \( \sqrt{N} \) 이하의 수의 배수만 지우면 된다.