素数判定ツール
最大40桁の数が素数かどうかを判定します。素因数分解、約数、前後の素数、範囲内のすべての素数も表示します。
素数判定の仕組み
素数とは、1より大きい整数で、約数がちょうど2つ（1と自分自身）しかない数です。2、3、5、7、11 は素数です。12（1、2、3、4、6、12）のように約数がもっと多い数は合成数です。0 と 1 は素数でも合成数でもありません。1より大きいすべての整数は、素数の積としてただ1通りに表せます。例：360 = 2³ × 3² × 5。
n を調べるには、√n までの各素数で割ります。n = a × b なら、a か b のどちらかは必ず √n 以下です。√n までのどの素数でも割り切れなければ、n は素数です。221 の場合、√221 ≈ 14.9 で、221 ÷ 13 = 17 なので、221 は素数ではありません。この計算機は1兆までの数に試し割りを使います。
大きな数では試し割りは遅すぎるため、ミラー・ラビン判定法を使います。すべての素数が持つ性質を、「基数」と呼ばれる複数のテスト値で確かめる方法です。最初の13個の素数を基数にすると、約 3.3 × 10²⁴ 未満のすべての数で正しいことが証明されています。それより大きい数では20個の基数を使い、結果は「確率的素数」と呼ばれます。合成数はポラードのロー法で因数に分解します。
免責事項: この計算ツールは、一般的な用途および教育目的のみで標準的な数学演算を行うものです。専門家による確認の代わりにはなりません — 財務申告、技術的な作業、学術提出物など、正確性が重要となる計算については、結果を必ずご自身で確認してください。
よくある質問
この計算機について
この素数判定ツールは、整数が素数かどうかをすぐに判定します。素数でない場合は、素因数分解と約数を表示します。前後の素数も表示し、双子素数やメルセンヌ素数を見つけ、1兆までの数では判定の手順も説明します。「範囲内の素数」タブでは、2つの数の間にあるすべての素数を一覧できます。
素数とは
素数とは、1より大きい整数で、約数がちょうど2つ（1と自分自身）しかない数です。最初の素数は 2、3、5、7、11、13 です。2 以外の偶数はすべて2で割り切れるため、2 は唯一の偶数の素数です。1より大きい整数で素数でないものを合成数と呼びます。0 と 1 は素数でも合成数でもありません。
素数はすべての整数のもとになる数です。算術の基本定理によると、1より大きいすべての整数は、順番を考えなければ、素数の積としてただ1通りに表せます。例えば 360 = 2³ × 3² × 5 です。合成数に対して表示されるのは、この素因数分解です。
判定の仕組み
小さい数・中くらいの数（1兆まで）：試し割り。 n を調べるには、√n までのすべての素数で割ります。n = a × b なら、a か b のどちらかは必ず √n 以下なので、これで十分です。どの素数でも割り切れなければ、n は素数です。1,000,000,007 の場合、√n ≈ 31,623 なので、31,622 までの 3,401 個の素数で割り、どれでも割り切れないことを確かめます。
大きな数：ミラー・ラビン判定法。 1兆を超える数にはミラー・ラビン判定法を使います。奇数の素数 p は、p − 1 = 2ˢ × d と書き、テスト値（基数）を p を法として d 乗するチェックに必ず合格します。合成数はほとんどの基数で不合格になります。最初の13個の素数（2〜41）を基数にすると、約 3.3 × 10²⁴ 未満のすべての数で正しいことが証明されています。それより大きい数では20個の基数を使い、結果を「確率的素数」と表示します。
素因数分解：ポラードのロー法。 大きな合成数を分解するには、まず小さな素因数を取り除き、次にポラードのロー法を使います。この方法は試し割りよりはるかに速く因数を見つけます。ただし、素因数がすべて非常に大きい数は、どんなコンピュータでも分解に何年もかかることがあります。その場合、ツールは分解できなかった部分をそのまま表示します。
範囲内の素数：ふるい。 範囲タブでは、区間版のエラトステネスのふるいを使います。√(終了) までの各素数の倍数を消していき、残った数が素数です。1兆までの好きな位置で、一度に最大100万個の数を調べられます。
計算例
- 221： √221 ≈ 14.9 なので、2、3、5、7、11、13 で割ります。221 ÷ 13 = 17 なので、221 = 13 × 17 は合成数です。奇数で5で終わらないため、221 を素数だと思う人がよくいます。
- 561： 561 = 3 × 11 × 17。最小のカーマイケル数で、共通の因数を持たないすべての基数でフェルマーの簡単な判定法をすり抜ける合成数です。ミラー・ラビン判定法にはこの弱点がありません。
- 2,147,483,647： 2³¹ − 1 で、メルセンヌ素数であり、プログラミングの符号付き32ビット整数の最大値です。ツールは素数であることを確認し、メルセンヌ素数と表示します。
- 600,851,475,143： = 71 × 839 × 1,471 × 6,857。最大の素因数 6,857 は、有名なプログラミング問題（Project Euler 問題3）の答えです。
数が大きくなるほど素数は少なくなりますが、なくなることはありません。素数定理によると、n の近くでは、およそ ln(n) 個に1個が素数です。1兆の近くでは ln(10¹²) ≈ 27.6 なので、20万個の数の中に約 7,238 個の素数があるはずです。999,999,800,000 から 1,000,000,000,000 までには実際に 7,213 個あり、範囲タブで確かめられます。
素数が使われている場面
- インターネットのセキュリティ： RSA暗号は、それぞれ数百桁ある2つの秘密の素数を掛け合わせます。積は誰でも見られますが、現実的な時間で素因数分解できる方法は知られていないため、鍵が守られます。
- プログラミング： ハッシュテーブルでは、データを均等に分けるために素数個の枠を使うことがよくあります。競技プログラミングでは、素数 1,000,000,007 で割った余りを答えさせる問題がよく出ます。
- 数学の記録： GIMPS プロジェクトは非常に大きなメルセンヌ素数を探しています。2024年10月には、4100万桁を超える素数 2^136,279,841 − 1 を発見しました。
- 学習： 素数探し、因数の樹形図、約数の個数は学校で学ぶ基本で、詳しい手順で各割り算を確認できます。
- すぐに判定 — 最大40桁の整数を調べ、素数か、合成数か、どちらでもないか（0と1）を表示します。
- 素因数分解と約数 — 合成数を指数付きの素因数に分解し、約数の個数と約数そのものを表示します。
- 手順の表示 — 1兆までの数では、√n、調べた素数、答えを示す割り算を表示します。
- 範囲内の素数 — 2つの数の間のすべての素数を一覧します。1兆まで、一度に100万個の数まで調べられ、双子素数の組の数も表示します。
- 前後の素数と特別な素数 — 前の素数と次の素数を表示し、双子素数やメルセンヌ素数を見つけます。