에라토스테네스의 체
모래밭에서 자갈을 거르는 체처럼, 합성수를 털어내고 순수한 소수만 쏙 남기는 수학의 거름망이에요.
정의 소수(1과 자기 자신만으로 나누어떨어지는 1보다 큰 자연수)를 빠르고 정확하게 찾아내는 고대 그리스의 수학 알고리즘이에요. 마치 구멍 난 체를 털어 모래알만 남기고 자갈을 걸러내듯, 작은 소수부터 시작해 그 배수들을 차례대로 지워 나가며 소수들만 깨끗하게 골라내는 방법이에요.
왜 숫자를 하나씩 나누어보지 않을까요?
바닷가에서 모래성을 쌓으려고 고운 모래를 모을 때를 떠올려 보세요. 손으로 조약돌을 일일이 하나씩 골라내는 것은 시간도 오래 걸리고 손도 많이 가요. 대신 구멍이 숭숭 뚫린 체에 모래를 붓고 탈탈 흔들면 크고 거친 돌멩이만 한 번에 걸러낼 수 있죠.
수학에서 소수를 찾을 때도 마찬가지예요. 어떤 숫자가 소수인지 확인하려고 2부터 시작해 모든 수로 일일이 나누어보는 방법은 숫자가 커질수록 너무 많은 시간이 걸려요. 1부터 100까지만 해도 수많은 나눗셈을 반복해야 하거든요.
에라토스테네스는 바로 이 번거로운 나눗셈을 완전히 뒤집어 생각했어요. 숫자를 하나씩 검사하는 대신, 소수의 배수들을 한꺼번에 지워버리는 거름망을 만든 거예요. 1은 소수가 아니니 먼저 빼두고, 가장 작은 소수인 2를 찾은 뒤 2의 배수를 체로 거르듯 싹 지우는 것으로 탐색을 시작해요.
체를 흔들며 배수를 차례대로 털어내요
가장 먼저 살아남은 수 2는 소수로 확정하고 동그라미를 쳐요. 그리고 2를 제외한 2의 배수인 4, 6, 8, 10 같은 짝수들을 전부 지워요. 짝수라는 거대한 자갈 더미를 단 한 번의 과정으로 체 밖으로 털어낸 셈이에요.
이제 지워지지 않고 살아남은 다음 숫자인 3을 소수로 확정해요. 그다음에는 3을 제외한 3의 배수인 6, 9, 12, 15 등을 체에서 차례차례 지워나가요. 6이나 12처럼 이미 2의 배수로 지워진 수도 있지만, 9나 15처럼 새로 걸러지는 합성수도 나타나요.
4는 이미 지워졌으니 건너뛰고, 그다음 살아남은 5를 소수로 확정한 뒤 5의 배수를 지워요. 이런 식으로 살아남은 작은 수의 배수를 지우는 과정을 끈기 있게 반복하면, 합성수들이 모두 빠져나가고 결국 체 위에는 오직 순수한 소수들만 보석처럼 남게 돼요.
조금 더 정확히 말하면 — 끝까지 다 해볼 필요는 없어요
조금 더 정확히 말하면, 찾으려는 범위의 끝까지 모든 숫자의 배수를 일일이 지워볼 필요는 전혀 없어요. 찾고자 하는 최댓값에 루트(제곱근)를 씌운 값까지만 확인하면 소수 찾기가 완벽하게 끝나기 때문이에요.
예를 들어 100까지의 자연수 중에서 소수를 찾고 싶다면 100의 제곱근인 10까지만 배수를 지우면 돼요. 10보다 큰 소수인 11이나 13의 배수들은 이미 앞선 단계인 2, 3, 5, 7의 배수를 지울 때 모두 먼저 지워졌기 때문이에요. 11의 배수 중 100 이하인 22, 33, 55, 77 같은 수는 이미 앞선 소수들의 배수이기도 하거든요.
이 영리한 지름길 덕분에 계산해야 하는 양이 획기적으로 줄어들어요. 그래서 컴퓨터 프로그래밍에서도 수만 개나 수억 개에 달하는 거대한 범위의 소수 목록을 뽑아낼 때, 수천 년 전 고대 그리스 학자가 발명한 이 체 거르기 알고리즘을 여전히 핵심 기술로 활용하고 있어요.
🤔 흔한 오해
에라토스테네스의 체는 어떤 큰 수 하나가 소수인지 판별할 때 가장 좋은 방법이다.
특정 큰 숫자 하나만 판별할 때는 다른 소수 판별법이 더 효율적이에요. 에라토스테네스의 체는 '1부터 특정 범위까지의 모든 소수 목록'을 한꺼번에 구할 때 가장 강력한 방법이에요.
🧺 일상에서 만나요
소수를 찾을 때 수를 일일이 나누지 않고 소수의 배수들을 차례로 지워 소수만 남기는 효율적인 알고리즘이에요.