이 개념은 배수를 차례로 지워 소수만 남기는 방법으로, 중학교 소인수분해 단원의 활동으로 등장한다.
에라토스테네스의 체란 2 이상의 자연수 중에서 합성수를 순서대로 지워 나가, 지워지지 않고 남은 수들이 모두 소수가 되도록 걸러내는 방법이다. 마치 체로 곡식을 거르면 작은 알갱이는 빠져나가고 큰 알갱이만 남듯이, 배수(어떤 수의 곱셈표에 나오는 수)를 지우면 소수(1과 자기 자신만을 약수로 갖는 수)만 남는다고 해서 붙은 이름이다.
체를 흔들면 가루는 빠져나가고 덩어리만 남는다. 여기서 "가루"에 해당하는 것이 합성수다. 합성수는 반드시 자기보다 작은 어떤 소수의 배수이므로, 소수의 배수를 순서대로 지워 나가면 결국 더 이상 지울 수 없는 수, 즉 소수만 체 위에 남는다. 일일이 "이 수가 소수인가?"를 나눗셈으로 확인하는 대신, "이 수는 이미 지워졌는가?"만 확인하면 되므로 훨씬 빠르다.
1부터 $N$까지의 수 중 소수를 모두 찾고 싶다고 하자. 가장 단순한 방법은 각 수를 2, 3, 4, …로 하나하나 나누어 보는 것인데, 수가 많아질수록 나눗셈 횟수가 급격히 늘어나 비효율적이다. 더 나은 방법을 찾아보자.
핵심 관찰: 합성수는 반드시 자기보다 작은 소수를 약수로 갖는다. 예를 들어 12는 소수 2의 배수이고, 15는 소수 3의 배수이다. 그렇다면 거꾸로, "2의 배수를 모두 지우고, 3의 배수를 모두 지우고, 5의 배수를 모두 지우고…"를 반복하면, 지워지지 않고 남는 수는 어떤 소수의 배수도 아니므로 소수일 수밖에 없다.
언제 멈출 수 있을까? 어떤 합성수 $n$ ($n \le N$)을 $n = a \times b$ ($a \le b$)로 나누어 보면, $a \le b$이므로 $a \times a \le a \times b = n$, 즉 $a \le \sqrt{n} \le \sqrt{N}$이다. 다시 말해 합성수 $n$은 반드시 $\sqrt{N}$ 이하인 소수를 약수로 갖는다. 따라서
$$\sqrt{N} \text{ 이하의 모든 소수의 배수만 지우면}, \; N \text{까지의 합성수가 전부 지워진다.}$$
즉, 소수 $p$의 배수를 지울 때 $p$가 이미 $\sqrt{N}$보다 커졌다면 더 지울 필요가 없다. 이 사실 덕분에 체는 다음과 같은 절차로 완성된다.
1부터 30까지의 소수를 구해 보자. $\sqrt{30} \approx 5.48$이므로 5까지의 소수, 즉 2, 3, 5의 배수만 지우면 된다.
남은 수: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$ — 이것이 30 이하의 소수 전부다.
프로그래밍에서 "1부터 100만까지의 소수를 모두 구하라" 같은 문제를 풀 때, 각 수마다 나눗셈으로 소수 판정을 하면 시간이 매우 오래 걸린다. 이때 에라토스테네스의 체 알고리즘을 코드로 구현하면 배수를 지우는 단순한 반복문만으로 빠르게 소수 목록을 얻을 수 있어서, 암호 프로그램이나 계산기 앱에서 소수 후보를 미리 뽑아 둘 때 실제로 쓰인다.
에라토스테네스는 기원전 3세기 무렵 활동한 고대 그리스의 학자로, 오늘날 이집트 알렉산드리아의 도서관을 관리했던 인물이다. 그는 지구 둘레를 계산한 것으로도 유명하지만, 소수를 빠짐없이 찾아내는 체계적인 방법을 고안한 것으로도 널리 알려져 있다. 당시에는 큰 수 중에서 소수를 찾는 일이 하나하나 나눗셈을 시도해야 하는 번거로운 작업이었는데, 배수를 지워 나가는 그의 방법은 이 문제를 효율적으로 해결했고, 이후 그의 이름을 따 "에라토스테네스의 체"라고 불리게 되었다.