에라토스테네스의 체 생성기（무료）— 소수 목록・제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은 소수도 합성수도 아닌 특수한 수이므로 색칠 대상에서 제외합니다.

Tips

  • 에라토스테네스의 체는 2부터 시작해 소수의 배수를 차례로 지워 나가는 방식으로 N 이하의 모든 소수를 효율적으로 나열하는 알고리즘입니다.
  • 상한 N을 400 이하로 설정하면 어떤 소수가 어떤 수를 걸러냈는지 단계별로 확인할 수 있습니다.
  • 「제1,000,000번째 소수는 무엇인가」와 같은 큰 순번의 역검색에도 대응하여 자릿수가 큰 소수의 존재 확인에 편리합니다.
  • 생성된 소수 목록은 브라우저 내에서 그 자리에서 계산되므로 서버로 데이터가 전송되지 않습니다.

자주 묻는 질문

기원전 3세기 수학자 에라토스테네스가 고안했다고 전해지는 소수 판별법으로, 2부터 차례로 정수를 나열하고 소수의 배수를 기계적으로 지워 나가면 남은 수가 모두 소수가 되는 방식입니다. 단순한 작업의 반복만으로 소수를 구할 수 있어 컴퓨터 구현에도 적합합니다.

본 도구는 브라우저 내에서 계산하므로 상한은 1,000,000까지로 제한합니다. 그 이상의 범위를 다루면 계산량이 크게 늘어나 브라우저 동작이 무거워질 수 있기 때문입니다.

소수 정리를 이용해 제 N번째 소수의 대략적인 상한값을 추정한 뒤, 그 범위에서 에라토스테네스의 체를 실행해 정확히 구합니다. 제1,000,000번째까지의 역검색을 지원합니다.

계산 결과가 많을 경우 처음 1,000개까지만 표시하고 그 이후는 개수만 요약해서 보여줍니다. 단계별 시각화는 상한이 400 이하일 때만 지원합니다.
ツールくん

여담 ― 2000년 전 알고리즘이 지금도 쓰이는 이유

에라토스테네스의 체는 기원전 3세기 알렉산드리아 도서관의 관장을 지낸 고대 그리스 학자 에라토스테네스가 고안했다고 전해지는, 현존하는 가장 오래된 소수 생성 알고리즘 중 하나입니다. 2000년도 더 전에 고안된 방법이 오늘날에도 컴퓨터 과학 교재로 여전히 쓰이고 있다는 사실은 이 알고리즘의 단순함과 아름다움을 잘 보여줍니다.

체의 원리는 놀라울 만큼 단순합니다. 2부터 순서대로 수를 나열하고, 아직 지워지지 않은 가장 작은 수를 소수로 확정한 뒤 그 배수를 모두 지웁니다. 이 작업을 √N까지 반복하는 것만으로 N 이하의 모든 소수가 밝혀집니다. 하나의 수가 소수인지 개별적으로 판정하는 시험 나눗셈법보다, 목록을 한꺼번에 구하고 싶을 때 훨씬 효율적입니다.

거대한 소수를 찾는 경쟁은 지금도 계속되고 있으며, GIMPS（Great Internet Mersenne Prime Search）같은 분산 컴퓨팅 프로젝트가 수천만 자릿수를 넘는 메르센 소수를 계속 발견하고 있습니다. 에라토스테네스의 체 자체는 그렇게 거대한 소수를 찾는 데 쓰이지는 않지만, 그 기본 발상（배수를 기계적으로 제외한다）은 더 고도화된 소수 판정 알고리즘의 토대가 되기도 합니다.

모든 여담 보기

이 도구를 본 사람들이 함께 본 도구

소수 판별기（무료）— 소인수분해와 계산 과정까지 표시

숫자를 입력하면 소수인지 즉시 판별합니다. 시험 나눗셈 과정, 완전한 소인수분해, 이전·다음 소수까지 확인할 수 있는 무료 도구. 최대 1,000만까지 지원.

소인수분해 계산기 (2~1,000,000)

2부터 1,000,000까지 임의의 정수 N을 즉시 소인수분해합니다. 단계별 나눗셈, 약수 목록, 약수의 개수와 합을 표시합니다. 1~100 소인수분해 참조표 포함.

최대공약수・최소공배수 계산기

두 개의 양의 정수를 입력하면 유클리드 호제법으로 최대공약수（GCD）를 구하고, 그 계산 과정을 단계별로 표시합니다. 최소공배수（LCM）도 동시에 산출합니다.

모듈러 연산 계산기 (Mod 계산기)

기본 mod, 모듈러 덧셈/뺄셈/곱셈, 모듈러 거듭제곱(빠른 거듭제곱・반복 제곱법), 모듈러 역원(확장 유클리드 호제법)의 4가지 모드를 지원하는 모듈러 연산 계산기입니다. BigInt를 사용해 음수의 mod와 매우 큰 지수의 거듭제곱도 정...

중국인의 나머지 정리(CRT) 계산기 — 연립 합동식 풀기

x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂)… 형태의 연립 합동식을 중국인의 나머지 정리로 풉니다. 법(모듈러스)들이 서로소인지 자동으로 검증하고, 가장 작은 음이 아닌 해와 일반해를 구합니다.

오일러 파이 함수(φ, 토션트 함수) 계산기

정수 N(1〜1,000,000)을 입력하면 1부터 N까지 정수 중 N과 서로소인 개수(오일러 파이 함수 φ(N))를 소인수분해와 계산식과 함께 즉시 표시합니다. 1〜100의 φ(n) 조견표 포함.