에라토스테네스는 배수를 지우는 것만으로 소수를 모두 찾아내는 방법을 고안했어요.
아래 버튼을 눌러 배수를 하나씩 지워가며, 남는 수가 정말 소수인지 확인해봐요. 맨 끝에 도전 문제 하나가 있어요.
에라토스테네스(BC 276~194)는 이집트 알렉산드리아 도서관의 사서였어요. 그는 2부터 어떤 수까지의 소수를 찾을 때, 소수를 직접 찾는 대신 소수가 아닌 수를 지워나가는 기발한 방법을 생각해냈어요 — 그래서 이름이 "체"(sieve, 거르는 도구)예요.
2의 배수를 지우고, 남은 것 중 가장 작은 수(3)의 배수를 지우고… 이렇게 반복하면 끝까지 안 지워진 수가 전부 소수예요.
100까지의 소수를 찾는데 2, 3, 5, 7의 배수만 지우면 충분해요. 왜냐하면 100보다 작은 합성수는 반드시 10(=√100) 이하의 소인수를 가지거든요 — 두 인수가 모두 10보다 크면 곱이 100을 넘어버려요.
이 알고리즘은 2200년이 지난 지금도 컴퓨터가 소수를 빠르게 찾을 때 그대로 쓰여요. 오래된 아이디어가 여전히 최신 기술의 재료가 되는 좋은 예예요.
2 × 3 × 5 × 7 + 1 = 211 이에요. 211 이 소수인지 확인하려면 어느 소수까지 나눠 보면 될까요? (그 가장 큰 소수를 적어 주세요)
💡 앞 절에서 봤듯이 √211 까지만 확인하면 돼요.
💡 14² = 196, 15² = 225 이니 √211 은 14 와 15 사이예요.
💡 14 이하의 소수는 2, 3, 5, 7, 11, 13 — 이 중 가장 큰 것이에요.