素数の判定と素因数分解

機能

• 5 通りの用途：判定・分解・N 番目の素数・範囲の列挙・ランダム生成
• ミラー-ラビン法による判定：18 桁でもミリ秒単位。平方根までの試し割りは不要
• 3.3×10²⁴ 未満の判定は決定的。超える場合は確率的判定であることを表示
• 素因数分解は Pollard rho を使用。大きな素数の積も分解できます
• 素数でない場合は最小の素因数を示すので、確認できます
• 分解は各素因数と指数を並べ（`2^3 × 3^2 × 5`）、個別にコピーできます
• カーマイケル数（フェルマーの小定理を騙す合成数）も見破ります
• 範囲の列挙は最大 500 個まで。超えた分は件数を明示します
• すべて端末内で計算し、外部サービスに依存しません

使い方

1. 用途を選びます：判定・分解・N 番目・範囲・ランダム生成
2. 対応する数値を入力します（範囲とランダムでは範囲が必要です）
3. 結果は即座に表示されます。行のコピーボタンで取り出せます

よくある質問

「確率的判定」とは何ですか？間違うことはありますか？

ミラー-ラビン法は確率的アルゴリズムですが、基底を固定するとある範囲に反例が存在しません —— 最初の 12 個の素数（2 から 37）を基底にすると、3.3×10²⁴ 未満の合成数は素数を装えないことが証明されています。したがってその範囲では結果は決定的です。それを超えても信頼性は極めて高く（誤り率は 4⁻¹² 未満）、単に数学的な証明ではなくなるため、ツールがその旨を表示します。

何桁まで分解できますか？

上限は 18 桁です。分解は小さい素数での試し割り、Pollard rho、ミラー-ラビン法の組み合わせで、18 桁（約 60 ビット）の 2 つの素数の積は通常 1 秒以内に解けます。それを超える場合は素直に断り、理由を説明します —— 数分間回り続けるページは、「大きすぎます」の一言よりはるかに悪いからです。

最初の素数が 1 ではなく 2 なのはなぜですか？

1 は定義上素数ではないからです（素数は正の約数をちょうど 2 つ持ちますが、1 は 1 つしかありません）。したがって最初の素数は 2 で、2, 3, 5, 7, 11… と続きます。このツールは 0 と 1 についても「素数ではない」と明示し、「最小の素因数は 1」などとは書きません —— 1 は素数ではないので、それは誤った表示です。