에라토스테네스의 체 생성기（무료）— 소수 목록・제N번째 소수 검색
상한 N을 입력하면 에라토스테네스의 체 알고리즘으로 소수 목록을 단계별로 시각화하며 생성합니다. 1~100 조견표에 더해 최대 100만 범위・제100만 번째 소수와 같은 큰 순번의 역검색도 지원하는 무료·브라우저 완결형 도구입니다.
1〜100의 에라토스테네스의 체（조견표）
녹색 칸이 소수이며, 나머지는 체에 의해 걸러진 합성수입니다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 |
| 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
| 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 |
| 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 |
| 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |
| 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 |
| 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
1은 소수도 합성수도 아닌 특수한 수이므로 색칠 대상에서 제외합니다.
에라토스테네스의 체란
에라토스테네스의 체는 기원전 3세기 그리스의 학자 에라토스테네스에서 이름을 딴, 소수를 찾기 위한 고전적인 알고리즘입니다. 발상은 놀랄 만큼 단순해서, 2부터 차례로 「아직 지워지지 않은 수」를 소수로 확정하고 그 배수를 모두 지워 나가기만 하면 됩니다. 2의 배수를 지우고, 다음으로 남은 3의 배수를 지우고, 5의 배수를 지우고——이 조작을 상한의 제곱근까지 반복하면 지워지지 않고 남은 수가 모두 소수가 됩니다.
이 도구는 상한 N을 지정하기만 하면 최대 100만까지의 소수 목록을 생성합니다. 체로 걸러 내는 과정을 단계별로 표시하기 때문에, 알고리즘이 「어떤 소수로 어떤 수를 지웠는지」를 눈으로 따라갈 수 있습니다. 나아가 「N번째 소수는 무엇인가」라는 역방향 검색에도 대응하여, 100만 번째 같은 큰 순위도 조사할 수 있습니다. 모두 브라우저 안에서 계산하므로 입력한 값이 어딘가로 전송되는 일은 없습니다.
소수 목록을 생성하는 순서
- 상한 N을 입력합니다 2 이상 1,000,000 이하의 정수를 지정합니다. 우선 100 같은 작은 값으로 시험해 보면 체의 구조가 잘 보입니다.
- 소수의 개수와 최대 소수를 확인합니다 N 이하에 소수가 몇 개 있는지(π(N))와, N 이하에서 가장 큰 소수가 표시됩니다.
- 걸러 내는 단계를 따라갑니다 상한이 작은 경우에는 어떤 소수를 써서 어떤 수를 지웠는지가 단계마다 표시됩니다.
- N번째 소수를 역으로 찾습니다 순위를 입력하면 그 순위에 해당하는 소수를 구할 수 있습니다.
더 잘 활용하기 위한 팁
- 에라토스테네스의 체는 2부터 시작해 소수의 배수를 차례로 지워 나가는 방식으로 N 이하의 모든 소수를 효율적으로 나열하는 알고리즘입니다.
- 상한 N을 400 이하로 설정하면 어떤 소수가 어떤 수를 걸러냈는지 단계별로 확인할 수 있습니다.
- 「제1,000,000번째 소수는 무엇인가」와 같은 큰 순번의 역검색에도 대응하여 자릿수가 큰 소수의 존재 확인에 편리합니다.
- 생성된 소수 목록은 브라우저 내에서 그 자리에서 계산되므로 서버로 데이터가 전송되지 않습니다.
이럴 때 쓸 수 있습니다
알고리즘 학습
계산량 O(n log log n)의 대표적인 예로 교과서에 반드시 등장합니다. 실제 움직임을 보면서 이해를 다질 수 있습니다.
프로그래밍 구현을 검증할 때
직접 작성한 체의 구현이 올바른 소수열을 돌려주는지 이 도구의 출력과 맞춰 확인할 수 있습니다.
소수의 분포를 살펴볼 때
상한을 바꿔 가며 π(N)의 증가를 보면, 소수 정리가 말하는 「N / log N을 대략 따른다」는 경향을 체감할 수 있습니다.
암호 관련 주제의 사전 조사
RSA 같은 공개키 암호는 큰 소수에 의존합니다. 소수가 어느 정도 밀도로 존재하는지를 파악하는 입구가 됩니다.
소수와 체의 용어
- 소수
- 1과 그 수 자신 외에 양의 약수를 갖지 않는, 2 이상의 자연수입니다. 1은 소수에 포함하지 않습니다.
- 합성수
- 소수가 아닌 2 이상의 자연수입니다. 체에서 지워지는 것이 바로 이 수들입니다.
- π(N)
- N 이하의 소수 개수를 나타내는 함수로, 소수 계량 함수라고 부릅니다.
- 걸러 내기
- 소수의 배수에 표시를 해 후보에서 제외하는 조작입니다. 알고리즘 이름의 유래가 되었습니다.
- 제곱근까지면 충분한 이유
- N의 제곱근을 넘는 소수의 배수는 그보다 작은 소수의 배수로 이미 지워져 있기 때문입니다.
- 소수 정리
- π(N)이 N / log N에 점근한다는 정리입니다. 소수가 드물어지는 속도를 말해 줍니다.
자주 묻는 질문
여담 ― 2000년 전 알고리즘이 지금도 쓰이는 이유
에라토스테네스의 체는 기원전 3세기 알렉산드리아 도서관의 관장을 지낸 고대 그리스 학자 에라토스테네스가 고안했다고 전해지는, 현존하는 가장 오래된 소수 생성 알고리즘 중 하나입니다. 2000년도 더 전에 고안된 방법이 오늘날에도 컴퓨터 과학 교재로 여전히 쓰이고 있다는 사실은 이 알고리즘의 단순함과 아름다움을 잘 보여줍니다.
체의 원리는 놀라울 만큼 단순합니다. 2부터 순서대로 수를 나열하고, 아직 지워지지 않은 가장 작은 수를 소수로 확정한 뒤 그 배수를 모두 지웁니다. 이 작업을 √N까지 반복하는 것만으로 N 이하의 모든 소수가 밝혀집니다. 하나의 수가 소수인지 개별적으로 판정하는 시험 나눗셈법보다, 목록을 한꺼번에 구하고 싶을 때 훨씬 효율적입니다.
거대한 소수를 찾는 경쟁은 지금도 계속되고 있으며, GIMPS（Great Internet Mersenne Prime Search）같은 분산 컴퓨팅 프로젝트가 수천만 자릿수를 넘는 메르센 소수를 계속 발견하고 있습니다. 에라토스테네스의 체 자체는 그렇게 거대한 소수를 찾는 데 쓰이지는 않지만, 그 기본 발상（배수를 기계적으로 제외한다）은 더 고도화된 소수 판정 알고리즘의 토대가 되기도 합니다.