소수를 찾으라고 하면 보통 수를 하나씩 붙잡고 “이 수가 무엇으로 나누어떨어지는가”를 따집니다. 에라토스테네스의 체는 방향이 반대입니다. 소수를 직접 찾지 않고, 소수가 아닌 수를 지워서 남는 수를 모읍니다. 체에 곡식을 거르면 알갱이가 남듯이, 배수를 걸러 내면 소수만 남는다는 생각입니다.
이 글에서는 이 방법이 어떤 기록으로 전하는지 먼저 확인하고, 1부터 100까지 실제로 걸러 보면서 지우기를 몇 번 하는지 세어 보았습니다. 마지막에는 1000만까지 늘려 하나씩 나눠 보는 방법과 작업량을 비교했습니다.
에라토스테네스의 책이 아니라 니코마코스의 책에 남은 방법
에라토스테네스는 기원전 3세기 알렉산드리아에서 활동한 학자로, 해 그림자로 지구 둘레를 계산한 일로 더 유명합니다. 그런데 그가 직접 쓴 수학 저술은 전하지 않습니다. 오늘날 ‘에라토스테네스의 체’라고 부르는 방법은 약 400년 뒤인 서기 100년 무렵 니코마코스가 쓴 《산술 입문》 1권 13장에 설명이 남아 있고, 니코마코스가 이 방법을 에라토스테네스의 것으로 소개합니다.
니코마코스의 설명은 현대 교과서와 조금 다릅니다. 2를 제외한 짝수는 소수가 될 수 없으므로 처음부터 3 이상의 홀수만 늘어놓습니다. 그다음 3에서 출발해 두 개를 건너뛰고 세 번째 수를 표시하고, 5에서는 네 개를, 7에서는 여섯 개를 건너뜁니다. 홀수만 적힌 줄에서 이렇게 세면 표시되는 수는 각각 3, 5, 7의 홀수 배수가 됩니다.
3에서 출발, 두 개 건너 세 번째마다 표시 3, 5, 7, [9], 11, 13, [15], 17, 19, [21], 23, 25, [27] … 5에서 출발, 네 개 건너 다섯 번째마다 표시 5, 7, 9, 11, 13, [15], 17, 19, 21, 23, [25], 27, 29, 31, 33, [35] …
같은 방법을 100까지 그대로 따라 해 보면 홀수 49개(3~99)를 적고, 3·5·7에서 각각 16번, 9번, 6번 모두 31번 표시하게 됩니다. 15, 21, 35, 45, 63, 75처럼 두 소수의 공배수인 6개는 두 번 표시되므로 실제로 지워지는 홀수는 25개입니다. 남은 홀수 24개에 2를 더하면 100까지의 소수 25개가 됩니다.
1부터 100까지 직접 걸러 보기
이번에는 오늘날 흔히 설명하는 방식대로 2부터 100까지 모든 수를 적고 걸러 보았습니다. 2의 배수를 지우고, 남은 수 가운데 가장 작은 3의 배수를 지우고, 다시 남은 5와 7의 배수를 지우는 순서입니다. 각 소수의 배수는 그 소수의 제곱부터 지우기 시작했습니다. 이유는 아래에서 따로 설명합니다.
| 소수 | 지우기 시작 | 지운 횟수 | 그 단계에서 새로 지운 수 |
|---|---|---|---|
| 2 | 4 | 49번 | 49개 |
| 3 | 9 | 31번 | 16개 |
| 5 | 25 | 16번 | 6개 |
| 7 | 49 | 8번 | 3개 |
| 합계 | 104번 | 74개 |
지운 횟수와 지워진 수의 개수가 다른 이유는 한 수가 여러 번 지워지기 때문입니다. 계산해 보면 100까지의 합성수 가운데 25개가 두 번 이상 지워졌고, 30·60·70·84·90은 세 번이나 지워졌습니다. 예를 들어 30은 2의 배수, 3의 배수, 5의 배수를 지울 때마다 다시 표시됩니다. 체가 낭비하는 부분은 이 겹치는 지우기뿐이고, 그 양은 뒤에서 보듯 수가 커져도 크게 늘지 않습니다.
10까지만 확인하면 되는 이유와 제곱부터 지우는 이유
100까지 거를 때 11, 13, 17 같은 소수의 배수는 지울 필요가 없습니다. 100 이하의 합성수 n을 두 수의 곱 a×b로 쓰면, a와 b가 둘 다 10보다 클 수는 없습니다. 둘 다 10보다 크면 곱이 100을 넘기 때문입니다. 따라서 100 이하의 합성수는 반드시 10 이하의 소인수, 즉 2·3·5·7 가운데 하나를 가집니다. 일반적으로 n까지 거를 때는 √n 이하의 소수만 확인하면 됩니다.
같은 논리로 각 소수 p의 배수를 p²부터 지워도 됩니다. p보다 작은 배수 2p, 3p, …, (p−1)p는 p보다 작은 소인수를 가지고 있으므로 앞 단계에서 이미 지워졌습니다. 7의 배수를 예로 들면 14·21·28·35·42는 2, 3, 5를 거를 때 사라졌고, 7이 처음 지우는 수는 49입니다. 2p부터 지우면 100까지 113번, p²부터 지우면 104번으로, 이 작은 규칙만으로도 지우기가 9번 줄었습니다.
수를 키우면: 1000만까지 나눗셈과 비교
체가 왜 좋은 방법인지는 범위를 넓혀야 드러납니다. 같은 범위에서 수를 하나씩 붙잡고 √x 이하의 소수로 차례로 나눠 보는 방법(나누어떨어지면 바로 멈춤)과 비교해 보았습니다. 두 방법 모두 파이썬으로 실제 연산 횟수를 셌습니다.
| 범위 n | 소수 개수 | 체: 지우기 횟수 | 나눗셈 횟수 | 수 하나당(체 / 나눗셈) |
|---|---|---|---|---|
| 100 | 25 | 104 | 181 | 1.04 / 1.81 |
| 1,000 | 168 | 1,411 | 2,801 | 1.41 / 2.80 |
| 1만 | 1,229 | 16,981 | 43,753 | 1.70 / 4.38 |
| 10만 | 9,592 | 193,078 | 744,436 | 1.93 / 7.44 |
| 100만 | 78,498 | 2,122,048 | 13,927,402 | 2.12 / 13.93 |
| 1000만 | 664,579 | 22,850,051 | 286,144,938 | 2.29 / 28.61 |
100까지에서는 두 방법의 차이가 2배도 되지 않습니다. 1000만까지 가면 체는 수 하나당 평균 2.3번 지우기로 끝나지만 나눗셈은 28.6번이 필요해 12배 넘게 벌어집니다. 체의 작업량은 대략 n×ln(ln n)에 비례해 아주 느리게 늘어나는 반면, 나눗셈은 큰 소수 하나를 확인할 때마다 그 제곱근 아래의 소수를 전부 시험해야 하기 때문입니다.
대신 체에는 대가가 있습니다. 걸러야 할 수를 처음부터 모두 적어 두어야 합니다. 1000만까지 거르려면 1000만 칸짜리 표가 필요하지만, 나눗셈은 지금 확인하는 수 하나만 있으면 됩니다. 파피루스에 수를 적던 시대라면 100이나 1000까지는 체가 편했겠지만 훨씬 큰 범위에서는 적을 공간이 먼저 문제가 되었을 것입니다. 현대 컴퓨터에서도 체를 구간별로 나눠 메모리를 아끼는 방법이 쓰이는 이유가 같습니다.
남은 소수는 점점 드물어진다
표의 소수 개수를 비율로 바꾸면 100까지는 네 수 가운데 하나(25%)가 소수지만, 1000만까지는 약 6.6%만 소수입니다. 소수가 끝없이 있다는 사실은 이미 유클리드의 《원론》 9권 명제 20에 증명되어 있지만, 얼마나 드물어지는지는 고대 수학이 다루지 못한 문제였습니다.
19세기 말에 증명된 소수 정리는 n까지의 소수 개수가 대략 n/ln n이라고 말합니다. 직접 센 개수를 이 값으로 나누면 100에서 1.15, 1만에서 1.13, 1000만에서 1.07로 아주 천천히 1에 다가갑니다. 에라토스테네스의 체는 이런 규칙을 찾기 위해 소수 목록을 대량으로 만드는 도구로도 2천 년 넘게 쓰였습니다.
계산 방법과 참고 자료
표와 그래프의 모든 수치는 정보호수가 파이썬으로 체와 나눗셈을 직접 구현해 연산 횟수를 센 결과입니다. 체는 각 소수의 제곱부터 지우는 방식, 나눗셈은 √x 이하의 소수로 나누다 나누어떨어지면 멈추는 방식으로 계산했습니다. 니코마코스 방식(홀수만 적는 방식)의 횟수는 별도로 셌습니다.
- Nicomachus of Gerasa, 《Introduction to Arithmetic》, M. L. D’Ooge 영역(1926), 공개 열람본: 1권 13장, 체 설명
- 《Dictionary of Scientific Biography》 니코마코스 항목(세인트앤드루스대학교 수학사 아카이브, PDF): 니코마코스의 연대와 저술
- 유클리드, 《원론》 9권 명제 20: 소수는 어떤 개수보다도 많다(소수의 무한성)
같이 읽으면 좋은 글
- 에라토스테네스의 지구 둘레 계산을 1/50원과 5,000스타디온으로 따라가기
- 이집트의 두 배 곱셈은 얼마나 빨랐을까: 9,604가지 곱셈으로 세어 보니
- 《손자산경》의 70·21·15는 어떻게 나왔을까: 나머지 문제 105가지를 전부 확인해 보니
체의 핵심은 “찾기 어려운 것을 직접 찾지 말고, 찾기 쉬운 것을 지워라”라는 발상입니다. 소수 하나하나는 불규칙하게 흩어져 있지만 배수는 일정한 간격으로 늘어서 있습니다. 규칙적인 쪽을 다루어 불규칙한 쪽을 얻어 내는 이 방법이 2천 년 넘게 쓰인 이유입니다.