素数チェッカーとは？
任意の数が素数かどうかを即座に判定できます。合成数の場合は完全な素因数分解を表示します。範囲内の素数リスト生成、前後の素数の検索、素数パターンの探索も可能です。数学教育、暗号の基礎、数論に役立ちます。
入力に上限はありません。JavaScript の安全整数範囲に収まる数はより速い試し割りで判定し、それより大きい数は決定的な BigInt 版 Miller-Rabin に切り替わるため、暗号規模の素数も正確に判定できます。素因数分解は (84 → 2 × 42 → 2 × 21 → 3 × 7) のように一段ずつ木構造で表示し、非常に大きな合成数では 10^7 を超える残りの余因子をそれ以上分解せずそのまま表示します。範囲検索は 1000 万件まで結果をスクロール表示でき、第 N 番目の素数を直接求めることもできるので、プログラミングの問題や数論演習に向きます。
使い方
- 正の整数を入力して素数かどうか確認します。大きな数でも即座に結果が表示されます。
- 合成数の場合は完全な素因数分解ツリーが表示されます。素数の場合は直近の上下の素数が表示されます。
- 範囲検索で2つの数値の間にある全素数を一覧表示するか、最初のN個の素数を生成します。
使用するタイミング
- 数論や離散数学の宿題の答えを照合したいとき。
- ハッシュ関数や教材用の暗号サンプルで素数の法を選びたいとき。
- Project Euler や競技プログラミングの問題で最初の N 個の素数を生成したいとき。
結果
97を入力すると素数、84を入力すると素数ではなく因数は2²×3×7です。1〜100の全素数を生成するとその範囲の25個の素数が確認できます。
よくある質問
- とても大きな数を判定するのにどれくらいかかる?
- 通常の入力なら 10 ミリ秒を大きく下回ります。決定的 witness 付き Miller-Rabin は概ね O(log³ n) のモジュラー指数演算で済み、数十桁の数でも数十回の乗算で完了します。12 桁の数でも暗号規模の素数でも、UI は体感的に即時応答です。
- 素因数分解は常に一意?
- 一意です。算術の基本定理が「1 より大きい整数は順序を除いてただ一つの素因数分解を持つ」ことを保証します。本ツールは因数を昇順に並べ、重複は指数で表記し(84 = 2² × 3 × 7)、教科書通りの形にそろえます。
- 判定できる最大値は?
- 固定の上限はありません。JavaScript の安全整数範囲に収まる数はより速い試し割りで処理し、それより大きい入力は BigInt 版 Miller-Rabin が扱います。このテストは 3.3 × 10^24 未満のすべての数で正しさが証明されており、それをはるかに超えても極めて強力な確率的素数判定として機能するため、暗号規模の素数も余裕で判定できます。
- なぜ 0 と 1 は素数ではない?
- 素数とは「ちょうど 2 つの異なる正の約数を持つ正の整数」で、約数は 1 と自身です。1 は自身しか約数を持たないので該当せず、0 は約数が無限にあります。両者を除外すると素因数分解の一意性が例外なく成り立ちます。
- 素数は現実の暗号にどう関わる?
- RSA は約 1024 ビットの素数を 2 つ選び、積を公開鍵の一部にします。その積を再び 2 つの素数に分解するのが極めて困難であることが RSA の安全性の根拠です。素数判定自体は同じ桁数でも高速なので、鍵生成のボトルネックにはなりません。