에라토스테네스의 체
체로 거르듯 합성수를 지워 보세요
1부터 100까지 숫자가 적힌 표를 펼칩니다. 1을 지우고, 2를 남기고 2의 배수를 지우고, 3을 남기고 3의 배수를 지워 나갑니다.
7의 배수까지만 지우면 남은 모든 수가 소수가 됩니다. 왜 100까지의 수를 거르는 데 7까지만 확인하면 충분할까요?
이야기
?
Public domain · 위키미디어 공용
제11장에서 막대 하나로 지구를 잰 그 사람, 에라토스테네스가 이것도 만들었습니다. 알렉산드리아 도서관에는 파피루스가 산더미였고, 그는 목록 만드는 일에 익숙했습니다. 소수 찾기도 그에게는 목록 정리였습니다.
그런데 이천삼백 년 동안 이것보다 나은 방법이 나오지 않았습니다. 오늘도 컴퓨터가 「어떤 범위 안의 소수를 다 찾아라」를 할 때 쓰는 것은 여전히 이 체입니다. 다듬어지기는 했어도 뼈대는 그대로입니다.
다만 이 체가 못 하는 일이 하나 있습니다. 큰 수 하나가 소수인지만 알고 싶을 때입니다. 그때는 그 수까지 오는 모든 수를 걸러야 하니 쓸 수가 없고, 전혀 다른 방법이 필요합니다.
100까지 걸를 때 10에서 멈춰도 되는 까닭은 이렇습니다. 100 이하의 합성수는 반드시 두 수의 곱인데, 둘 다 10보다 크면 곱이 100을 넘기 때문입니다.
그러니 적어도 하나는 10 이하입니다. 10까지의 소수 2, 3, 5, 7로 걸러 내면 합성수는 남김없이 걸립니다.
암호에 쓸 큰 소수를 찾는 첫 단계입니다. 이천이백 년 전 방법인데 지금도 쓰입니다.
컴퓨터로 백만까지의 소수를 뽑을 때 이보다 간단하고 빠른 방법을 아직 못 찾았습니다.
계단 넷 — 같은 사실을 네 깊이로
100까지 표에서 배수를 지운다
모래를 체에 쳐서 굵은 돌을 걸러내듯 수를 거릅니다. 2의 배수(짝수), 3의 배수, 5의 배수, 7의 배수를 차례대로 색칠해 지웁니다.
구멍 난 체 사이로 빠져나가지 않고 끝까지 살아남은 숫자들인 2, 3, 5, 7, 11, 13, 17, 19, 23... 이 바로 더 이상 쪼개지지 않는 자연수의 씨앗, 소수입니다.
배수를 지워 보세요
앞쪽에서 4번만 체를 쳤는데 100까지 불필요한 돌멩이가 싹 다 걸러진다
√n 까지만 지우면 되는 까닭
합성수 은 두 수의 곱 로 나타납니다. 만약 둘 다 보다 크다면 곱은 을 넘어버립니다.
따라서 합성수는 반드시 이하인 소인수를 적어도 하나 가져야 합니다. 100까지의 수는 이하의 소수인 2, 3, 5, 7의 배수만 지우면 검사가 끝납니다.
어디까지 지우면 될까요
만 개나 되는 숫자를 검사할 때 백까지만 체질을 하면 만 개 전체가 한 방에 정리된다
소수의 개수 어림
에라토스테네스의 체는 이하의 모든 소수를 시간 복잡도 만에 찾아내는 효율적인 알고리즘입니다.
가우스와 르장드르는 이하의 소수 개수 가 대략 에 점근한다는 소수 정리(Prime Number Theorem)를 제시하였으며, 이는 체의 제거 비율 분석에서 출발했습니다.
소수는 얼마나 드문가
제멋대로 흩어진 소수 개수를 세어보면 부드러운 미끄럼틀 곡선과 소름 돋게 일치한다
체 이론
현대 정수론에서 체 방법론은 브룬의 체(Brun's sieve), 셀베르그의 체(Selberg's sieve)를 거쳐 현대 체 이론(Sieve Theory)으로 발전했습니다.
천징룬의 정리(충분히 큰 짝수는 소수와 두 소수의 곱의 합)와 장이탕 및 제임스 메이나드의 쌍둥이 소수 간격 유한성 증명은 모두 이 체 이론의 정교한 변형을 통해 달성되었습니다.
체가 얼마나 걸러 내나
모든 숫자의 덧셈 탑에 소수 필터를 하나씩 걸러 곱해주면 마지막에 정확히 1이 남는다
풀어 보기
소수 판별과 에라토스테네스의 체. 1부터 50까지의 자연수 중에서 소수를 찾으려고 한다.
(1) 1부터 50까지의 합성수를 모두 지우기 위해 배수를 확인해야 하는 소수를 모두 쓰시오.
(2) 1부터 50까지의 자연수 중 소수의 개수 을 구하시오.
(3) 어떤 세 자리 수 143 이 소수인지 판별하려 할 때, 나누어 떨어지는지 검사해야 하는 소수들을 모두 쓰고 소수인지 합성수인지 판정하시오.
(1) 이므로 2, 3, 5, 7 입니다. (2) 개수는 15개, (3) 합성수입니다.
답과 풀이 보기
(1) 이므로 2, 3, 5, 7 의 배수만 지우면 됩니다.
합성수 에서 두 인수가 모두 보다 클 수는 없기 때문입니다.
(2) 남는 소수는
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 — 개
(3) 이므로 2, 3, 5, 7, 11 만 검사하면 됩니다.
으로 나누어떨어지므로 — 합성수입니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
「걸러 내기」는 계산의 기본 수법입니다.
- 암호 — 큰 소수를 빨리 찾는 일이 인터넷 보안의 바탕입니다
- 해시·중복 걸러내기 — 많은 자료에서 원하는 것만 남기는 방식이 닮았습니다
- 직접 해 보기 — 모눈종이에 100까지 적고 지워 보면 십 분이면 됩니다
이어지는 장
배수들을 모두 지워 버려도 체 위에 무한히 걸러져 남는 소수의 신비는, 아무리 큰 소수를 가져와도 그보다 더 큰 소수가 반드시 존재한다는 유클리드의 귀류법 증명으로 뻗어 나갑니다 — 제113장에서 무한한 소수의 바다를 만나보세요.
영감을 받은 곳
기원전 3세기 알렉산드리아의 학자 에라토스테네스가 고안한 소수 탐색법으로, 1세기 니코마코스의 『산술 입문』에 기록되어 전해집니다.