# 에라토스테네스의 체 분야: 대수 학교급: 중등 교육과정: 배수를 차례로 지워 소수만 남기는 방법. 교과서의 소인수분해 단원 활동으로 등장한다. 정식 URL: https://pi.devxdev.xyz/wiki/math/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 --- > 이 개념은 배수를 차례로 지워 소수만 남기는 방법으로, 중학교 소인수분해 단원의 활동으로 등장한다. ## 정의 **에라토스테네스의 체**란 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. 1은 소수도 합성수도 아니므로 목록에서 제외한다. 2. 남은 수 중 가장 작은 수 2를 소수로 확정하고, $4, 6, 8, \dots$ 즉 2의 배수를 모두 지운다. 3. 지워지지 않은 다음 수 3을 소수로 확정하고, $9, 12, 15, \dots$ 즉 3의 배수를 모두 지운다. (6은 이미 2의 배수로 지워졌으므로 3의 배수 중 $3\times3=9$부터 지우면 충분하다.) 4. 이 과정을 지워지지 않은 다음 수가 $\sqrt{N}$보다 커질 때까지 반복한다. 5. 마지막까지 지워지지 않고 남은 수들이 $N$ 이하의 소수 전체이다. ## 예시 1부터 30까지의 소수를 구해 보자. $\sqrt{30} \approx 5.48$이므로 5까지의 소수, 즉 2, 3, 5의 배수만 지우면 된다. - **2의 배수 지우기**: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 - **3의 배수 지우기**(이미 지워진 것 제외): 9, 15, 21, 27 - **5의 배수 지우기**(이미 지워진 것 제외): 25 - 다음 지워지지 않은 수는 7인데, $7 > \sqrt{30}$이므로 여기서 멈춘다. 남은 수: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$ — 이것이 30 이하의 소수 전부다. ## 🌍 실생활 예시 프로그래밍에서 "1부터 100만까지의 소수를 모두 구하라" 같은 문제를 풀 때, 각 수마다 나눗셈으로 소수 판정을 하면 시간이 매우 오래 걸린다. 이때 에라토스테네스의 체 알고리즘을 코드로 구현하면 배수를 지우는 단순한 반복문만으로 빠르게 소수 목록을 얻을 수 있어서, 암호 프로그램이나 계산기 앱에서 소수 후보를 미리 뽑아 둘 때 실제로 쓰인다. ## ⚠️ 흔한 실수 - **소수 자신까지 지워 버리는 실수**: "3의 배수를 지운다"고 배우면 3, 6, 9, …를 전부 지워야 한다고 착각하기 쉽다. 하지만 3 자신은 소수이므로 남겨 두고, $6 = 2\times3$부터 지워야 한다. - **끝까지 다 지워야 한다고 생각하는 실수**: $\sqrt{N}$을 넘는 소수의 배수까지 확인하려 하면 불필요한 계산이 늘어난다. 유도 과정에서 보였듯, $\sqrt{N}$보다 큰 소수의 배수는 이미 더 작은 소수에 의해 전부 지워져 있으므로 확인할 필요가 없다. - **"소수"라는 말을 헷갈리는 실수**: 한글로 "소수"는 소수(素數, prime number)와 소수(小數, decimal, 0.3 같은 수)가 발음이 같아 혼동하기 쉽다. 이 문서의 "소수"는 항상 약수가 1과 자기 자신뿐인 자연수를 뜻한다. ## 확인 문제 1. 1부터 20까지의 자연수에 에라토스테네스의 체를 적용하여 소수를 모두 구하시오. 2. 1부터 100까지의 소수를 구하려면 몇까지의 배수만 지우면 충분한지, 그리고 그 이유를 $\sqrt{100}$을 이용해 설명하시오. 3. 49는 소수인지 합성수인지 판정하고, 그 근거를 $\sqrt{49}=7$과 관련지어 설명하시오. 정답 보기: 1. 2, 3, 5, 7, 11, 13, 17, 19. ($\sqrt{20}\approx4.47$이므로 2, 3의 배수만 지우면 충분하다.) 2. $\sqrt{100}=10$이므로 10 이하의 소수, 즉 2, 3, 5, 7의 배수만 지우면 충분하다. 100 이하의 어떤 합성수든 $\sqrt{100}=10$ 이하인 소수를 약수로 반드시 가지기 때문이다. 3. 합성수다. $7 = \sqrt{49}$이고 $49 = 7\times7$이므로 7이 49의 약수이며, 1과 49 외의 약수가 존재하므로 소수가 아니다. ## 📜 역사 에라토스테네스는 기원전 3세기 무렵 활동한 고대 그리스의 학자로, 오늘날 이집트 알렉산드리아의 도서관을 관리했던 인물이다. 그는 지구 둘레를 계산한 것으로도 유명하지만, 소수를 빠짐없이 찾아내는 체계적인 방법을 고안한 것으로도 널리 알려져 있다. 당시에는 큰 수 중에서 소수를 찾는 일이 하나하나 나눗셈을 시도해야 하는 번거로운 작업이었는데, 배수를 지워 나가는 그의 방법은 이 문제를 효율적으로 해결했고, 이후 그의 이름을 따 "에라토스테네스의 체"라고 불리게 되었다. ## 관련 개념 - 소수 - 약수와 배수 - 소인수분해 - 소수와 합성수 - 최대공약수와 최소공배수 --- 관련 개념: - 소수 (/wiki/math/%EC%86%8C%EC%88%98) - 약수와 배수 (/wiki/math/%EC%95%BD%EC%88%98%EC%99%80_%EB%B0%B0%EC%88%98) - 소인수분해 (/wiki/math/%EC%86%8C%EC%9D%B8%EC%88%98%EB%B6%84%ED%95%B4) - 소수와 합성수 (/wiki/math/%EC%86%8C%EC%88%98%EC%99%80_%ED%95%A9%EC%84%B1%EC%88%98) - 최대공약수와 최소공배수 (/wiki/math/%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98%EC%99%80_%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98)