素数判定＆素因数分解

使い方

正の整数を入力してください。入力と同時に素数判定を行い、合成数の場合は素因数分解、また前後の素数も表示されます。6k ± 1方式の試し割りを使用しているため、数兆の範囲までほぼ遅延なく計算できます。

素数とは

素数とは、1より大きい整数のうち、1と自分自身以外に正の約数を持たないものです。最初の素数は2, 3, 5, 7, 11, 13, 17, 19, 23, 29です。1より大きいすべての整数は素数の積として一意に表現できます（算術の基本定理）。暗号・数論・組合せ論における因数分解アルゴリズムの基礎となります。

判定の仕組み

0・1・負の整数は最初に除外し、2と3は直接trueとし、2と3の倍数を除外します。残りの候補は6k ± 1方式で試し割りします（3より大きい素数はすべて6k−1または6k+1の形なので、約数候補の2/3を飛ばせます）。試し割りの上限は√nです。素因数分解も同様のパターンで昇順に素因数を取り出します。

主な用途

• 数論・離散数学の宿題の答え合わせをする学生。
• 素数列・階乗関連パターン・オイラーのφ関数などを探索する数学愛好家。
• 素因数分解の例題を用意する教員。
• プログラミング中に小さな定数が素数かどうかをすばやく確認する開発者。
• パズル愛好家・競技プログラマーの事例検証。

ヒント

• 1は慣習的に素数ではありません（正の約数が2個ちょうど必要）。
• 2は唯一の偶数の素数です。
• 数が大きくなるほど素数の密度は低くなります（素数定理: n以下の素数は約n/ln(n)個）。
• 暗号用途の巨大数（数百桁）では試し割りは非現実的で、Miller-Rabinなどの確率的判定が使われます。本ツールは日常的な数値が対象です。
• 入力は14桁（10^14 − 1）に制限しています。試し割りをブラウザ上で快適に実行するためです。

プライバシー

すべての判定・因数分解はブラウザ内で完結します。入力した数値がサーバーに送信されたり保存されたりすることはありません。