에라토스테네스의 체
쉽게 풀면
1부터 100까지 숫자를 쭉 적어 놓고 소수를 찾는다고 해봅시다. 먼저 2는 남기고 2의 배수(4, 6, 8, ...)를 모두 지웁니다. 다음으로 지워지지 않고 남은 가장 작은 수인 3을 남기고 3의 배수를 모두 지웁니다. 이런 식으로 계속 "배수를 체로 걸러내듯" 지워 나가면, 끝까지 살아남는 숫자들이 바로 소수입니다. 마치 여러 겹의 체로 알갱이를 걸러 가장 굵은 것만 남기는 것과 비슷하다고 해서 "체(sieve)"라는 이름이 붙었습니다. 이 방법을 고안한 고대 그리스 수학자 에라토스테네스의 이름을 따서 붙여진 명칭입니다.
왜 중요한가
에라토스테네스의 체는 구현이 단순하면서도 일정 범위 안의 소수를 매우 빠르게 나열할 수 있어, 암호학·정수론 연구뿐 아니라 알고리즘 성능을 비교하는 실험 논문에서 기본 도구나 비교 기준으로 자주 등장합니다. 대규모 소수 목록이 필요한 암호키 생성, 소인수분해 기반 연산의 전처리 단계 등에서 이 알고리즘이 실질적으로 활용되기 때문에 응용 범위가 넓습니다.
논문에서는 이렇게 쓰입니다
이 문장은 암호학이나 알고리즘 논문에서, 특정 범위 안의 모든 소수를 빠르게 나열해야 할 때 이 고전적인 방법을 사용했다는 뜻입니다. 소인수분해나 암호키 생성처럼 소수가 필요한 여러 계산의 기초 단계로 자주 언급됩니다.
이 문장은 "범위가 너무 커서 한 번에 다 처리하기 어려운 경우, 구간을 나누어 체를 적용하는 방식으로 메모리는 아끼면서도 계산 속도는 크게 떨어뜨리지 않았다"는 뜻으로, 알고리즘 최적화 연구에서 흔히 쓰이는 표현입니다.
이 문장은 "여러 개의 처리 코어에 나누어 동시에 계산하도록 알고리즘을 바꾼 뒤, 실제로 얼마나 빨라지는지를 이 소수 찾기 알고리즘을 예로 들어 확인했다"는 뜻입니다.
조금 더 깊게 보면
기본적인 에라토스테네스의 체는 시간 복잡도가 대략 O(n log log n) 수준으로 알려져 있어 단일 정수의 소수 판별을 반복하는 방법보다 훨씬 효율적이지만, 범위 n이 매우 커지면 필요한 메모리 공간이 부담이 될 수 있습니다. 이를 보완하기 위해 전체 범위를 작은 구간으로 나누어 순차적으로 처리하는 세그먼트 체, 짝수를 애초에 배제하는 방식 등 다양한 변형이 쓰이며, 이런 최적화 기법들은 대규모 소수 생성이 필요한 실용적인 상황에서 자주 함께 언급됩니다.
주의할 점
에라토스테네스의 체는 정해진 범위 안의 모든 소수를 한 번에 찾는 방법이며, 하나의 수가 소수인지 아닌지만 개별적으로 판별하는 것과는 접근 방식이 다릅니다. 또한 큰 수 하나를 소인수분해하는 것과도 목적이 다른데, 소인수분해는 이미 정해진 하나의 수를 소수들의 곱으로 쪼개는 작업이고, 체는 범위 내의 소수 자체를 찾아내는 작업입니다.