素数判定機（無料）- 1000桁まで対応・素因数分解も

最大1000桁の数字が素数かどうかを瞬時に判定。素因数分解・前後の素数・試し割りの手順、そしてどの判定法で確定したかまで表示する無料ツールです。登録不要。

1000 未満の素数一覧（全 168 個）

2 3 5 7 11 13 17 19 23 29 31 37
41 43 47 53 59 61 67 71 73 79 83 89
97 101 103 107 109 113 127 131 137 139 149 151
157 163 167 173 179 181 191 193 197 199 211 223
227 229 233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349 353 359
367 373 379 383 389 397 401 409 419 421 431 433
439 443 449 457 461 463 467 479 487 491 499 503
509 521 523 541 547 557 563 569 571 577 587 593
599 601 607 613 617 619 631 641 643 647 653 659
661 673 677 683 691 701 709 719 727 733 739 743
751 757 761 769 773 787 797 809 811 821 823 827
829 839 853 857 859 863 877 881 883 887 907 911
919 929 937 941 947 953 967 971 977 983 991 997

1000 未満のこれ以外の数はすべて合成数で、1 と自分自身以外の約数を少なくとも 1 つ持ちます。

10 のべき乗ごとの素数の個数

以下の範囲 素数の個数 π(x) 素数の割合
10 4 40%
100 25 25%
1,000 168 16.8%
10⁴ 1,229 12.29%
10⁵ 9,592 9.59%
10⁶ 78,498 7.85%
10⁷ 664,579 6.65%
10⁸ 5,761,455 5.76%
10⁹ 50,847,534 5.08%
10¹⁰ 455,052,511 4.55%
10¹² 37,607,912,018 3.76%
10¹⁵ 29,844,570,422,669 2.98%

π(x) は素数計数関数で、x 以下の素数の個数を表します。割合は少しずつ小さくなっていき（x の付近ではおよそ ln(x) 個に 1 個が素数）、それでもゼロにはなりません。素数は無限に存在するからです。

素数判定機とは

素数判定機は、入力した整数が「1と自分自身以外に約数を持たない数」かどうかを調べるツールです。小さな数であれば手計算の試し割りで確かめられますが、暗号鍵の候補や数学コンテストで扱うような大きな数、何百桁にもなる数では試し割りは現実的な時間で終わりません。そのため、規模に応じて別の判定法を使い分ける必要があります。

このツールは最大1000桁までの整数に対応し、数の大きさに応じて最も速く、かつ数学的に信頼できる判定法を自動的に選びます。小さい数は試し割り法、約3.3×10²⁴未満はミラー・ラビン法による決定的な証明、それより大きい数はBaillie–PSW法による確率的素数の判定です。素因数分解・前後の素数・どの判定法で結論が出たかも合わせて表示します。

素数判定の使い方

  1. 整数を入力する 入力欄に最大1000桁までの整数を入力するか貼り付けます。カンマや空白は自動的に無視されます。
  2. 判定結果を確認する 素数・合成数・1という特殊なケースのいずれかが表示され、どの判定法で結論が出たかも併記されます。
  3. 詳細情報を見る 素因数分解・前後の素数・双子素数やメルセンヌ素数などの性質を確認できます。
  4. 試し割りの手順を辿る 小さめの数であれば、実際にどの割る数まで試したかを一覧表で確認できます。

使いこなすためのヒント

  • 素数とは、1 より大きい整数のうち、1 と自分自身以外に約数を持たない数です。2, 3, 5, 7, 11, 13, … と続き、この列は終わることがありません。
  • 素数かどうかを調べる最も基本的な方法が試し割り法です。2 から √N までの整数で順に割ってみます。√N で止めてよいのは、N = a × b と書けるなら小さい方の因数が必ず √N 以下になるからです。
  • 手計算でも多くの数はすぐに除外できます。2 以外の偶数、末尾が 5 の数、各桁の和が 3 の倍数になる数は、いずれも合成数です。また 3 より大きい素数は必ず 6k − 1 か 6k + 1 の形をしています。
  • 大きな数では試し割り法は現実的でないため、コンピューターはミラー・ラビン法やBaillie–PSW 法を使います。このページもそれらを実装しているので、最大 1000 桁の数を貼り付けても 1 秒以内に判定できます。
  • 1 は素数ではありません（定義に「1 より大きい」という条件があります）。また 2 は唯一の偶数の素数です。それより大きい偶数はすべて 2 で割り切れてしまいます。

活用シーン

宿題や数学コンテストの答え合わせ

証明問題や演習で「これは素数だ」とした数が本当に正しいかをすぐ確認できます。誤りなら素因数分解も一緒に表示されます。

暗号技術の仕組みを体験する

大きな候補数を入力し、RSA暗号などで使われる素数判定の考え方を、試し割り法とミラー・ラビン法／Baillie–PSW法の違いとして体感できます。

数の特別な性質を調べる

双子素数・ソフィー・ジェルマン素数・メルセンヌ素数・フェルマー素数に該当するかを、資料を調べずにその場で確認できます。

プログラミング学習・アルゴリズムの理解

試し割りの手順テーブルを見ながら、素数判定アルゴリズムがどう結論を出すのかを、自分で実装する前に理解できます。

用語集

素数
1より大きい整数のうち、1と自分自身以外に約数を持たない数。2, 3, 5, 7, 11, 13, … と無限に続きます。
合成数
1と自分自身以外にも約数を持つ整数。素数の積として表すことができます。
試し割り法
2から√Nまでの整数で順番に割ってみる判定法です。完全な証明になりますが、Nが大きいと現実的な時間で終わりません。
ミラー・ラビン法
Nを法とした1の平方根の性質を利用する判定法です。十分な数の底を使うと、約3.3×10²⁴未満の数に対して決定的な証明になります。
Baillie–PSW法
ミラー・ラビン法と強リュカ法を組み合わせた判定法です。決定的な証明ができないほど大きな数に使われ、これまで反例は見つかっていません。
確率的素数
Baillie–PSWのような強力な判定法を通過した数のことです。素数である可能性が極めて高いものの、数学的に完全な証明ではありません。
双子素数
11と13のように、差がちょうど2である素数の組です。無限に存在するかどうかは数学の未解決問題です。
メルセンヌ素数
2の p 乗引く1という形をした素数です。これまでに発見された最大級の素数の多くがこの形をしています。

よくある質問

1000 桁まで対応しています。10¹² 未満は試し割り法、3,317,044,064,679,887,385,961,981 未満は決定的なミラー・ラビン法、それ以上は Baillie–PSW 法で判定します。素因数分解と前後の素数の探索は、素数判定よりはるかに計算量が大きいため、対応範囲はこれより狭くなります。

およそ 3.3 × 10²⁴ を超える数の結果は Baillie–PSW 法によるもので、反例は 1 つも見つかっていませんが証明もされていません。実際には暗号ライブラリが依拠している判定法でもあるため、「確率的素数」という結果は極めて信頼できます。なお逆方向の判定に曖昧さはありません。合成数と表示された場合は、証拠か約数が実際に見つかっているので、それは証明です。

素数の定義が「1 より大きい整数」であるためです。1 を除外することで素因数分解の一意性が保たれます。もし 1 を素数に含めると、6 は 2 × 3 とも 1 × 2 × 3 とも 1 × 1 × 2 × 3 とも書けてしまい、算術の基本定理が成り立たなくなります。

2 は 1 と自分自身以外に約数を持たないため、定義を満たします。また唯一の偶数の素数でもあります。2 より大きい偶数はすべて 2 で割り切れるため、3 つ目の約数を持ってしまうからです。

存在しません。紀元前 300 年頃にユークリッドが素数の無限性を証明しています。有限個の素数を掛け合わせて 1 を足すと、その数はリストにない素因数を持つからです。あるのは「現在知られている最大の素数」だけで、その記録は更新され続けています。現在は 2024 年に発見された 2¹³⁶²⁷⁹⁸⁴¹ − 1 です。

平方根以下の素数（2, 3, 5, 7, 11, …）で順に割ってみてください。391 なら √391 ≈ 19.8 なので、2, 3, 5, 7, 11, 13, 17, 19 だけ試せば十分で、17 で割り切れて 391 = 17 × 23 と分かります。各桁の和が 3 の倍数なら 3 で割り切れる、といった判定法も役立ちます。
ツールくん

余談ですが ― 素数はなぜ重要なのか

素数はしばしば「数の原子」と呼ばれます。算術の基本定理によれば、1 より大きいすべての整数は素数の積としてただ一通りに表せます。つまり素数は、あらゆる整数を組み立てるための、それ以上分解できない部品ということです。上に表示される素因数分解が一意である理由もここにあり、360 は 2³ × 3² × 5 であって、それ以外の書き方はありません。

巨大な数が素数かどうかを「判定する」ことと「素因数分解する」ことは別の問題で、その違いの歴史は知っておくと面白いです。フェルマーの小定理を使えば高速な判定ができますが、どの底を使っても通り抜けてしまう合成数が存在します。その最小の例が 561 で、上のボタンから試せます（このような数をカーマイケル数といいます）。ミラー・ラビン法は途中で 1 の平方根を確認することでこの抜け穴をふさぎ、最初の 13 個の素数を底に使えば、約 3.3 × 10²⁴ 未満のすべての数に対して決定的な判定法になることが証明されています。それを超える範囲では、このページは強リュカ法を追加した Baillie–PSW 法を使います。この判定を通過する合成数はまだ 1 つも見つかっていませんが、証明はされていないため、非常に大きな数の結果は「確率的素数」と表示しています。

この「判定は簡単なのに分解は難しい」という非対称性が、現代の暗号技術を成り立たせています。HTTPS 通信や電子署名をいまも支える RSA 暗号は、大きな素数 2 つを掛け合わせて公開鍵を作ります。その積から元の素数を取り出すことは事実上不可能だと考えられているため、検証は一瞬でできるのに、分解はできないという状態が作れるわけです。このページでもその差を体感できます。1000 桁の数の素数判定はほぼ瞬時に終わりますが、30 桁の素数 2 つを掛けた 60 桁の合成数は、素因数分解しきれずに終わります。

素数には、数学で最も古くから残る未解決問題もあります。11 と 13、あるいは 1,000,000,000,061 と 1,000,000,000,063 のような双子素数が無限に存在するかどうかは、いまだに誰も知りません。素数そのものが尽きないことは紀元前 300 年頃にユークリッドが証明しているのに、です。記録更新の探索も続いています。GIMPS プロジェクトの参加者たちは 2^p − 1 という形のメルセンヌ数を手分けして調べており、現在知られている最大の素数は 2024 年に見つかった 2¹³⁶²⁷⁹⁸⁴¹ − 1 で、41,024,320 桁もあります。

関連する余談を読む

すべての余談を見る

このツールを見ている人は、こんなツールも見ています

エラトステネスの篩ジェネレーター（無料）- 素数一覧・第N番目の素数を検索

上限Nを指定するだけでエラトステネスの篩アルゴリズムを使い、素数の一覧をステップごとに可視化しながら生成。1から100の早見表に加え、最大100万までの範囲・第100万番目の素数のような大きな順位の逆引き検索にも対応した、登録不要...

素因数分解 計算機・ツール（無料・2〜100万対応）

素因数分解を計算する無料サイト・計算機です。「12825 の素因数分解」のような具体的な数値も含め、2〜1,000,000の任意の整数を入力するだけで分解ステップ・約数一覧・約数の個数と総和まで瞬時に自動計算。1〜100の素因数分解早見表も...

最大公約数・最小公倍数計算機

2つの正の整数を入力すると、ユークリッドの互除法で最大公約数（GCD）を求め、その計算過程をステップごとに表示します。最小公倍数（LCM）も同時に算出します。

合同式・モジュラー計算ツール（mod計算機）

基本のmod計算・加減乗算・べき乗（繰り返し二乗法）・モジュラー逆元（拡張ユークリッドの互除法）の4モードに対応した合同式計算機。負の数のmodや大きな指数のべき乗もBigIntで正確に計算します。

中国剰余定理（CRT）計算機 ― 連立合同式を解く

x ≡ a₁ (mod n₁)、x ≡ a₂ (mod n₂)…といった連立合同式を中国剰余定理で解く計算機。法が互いに素であるかを自動で検証し、最小の非負整数解と一般解を求めます。

オイラーのφ関数（トーシェント関数・互いに素な数の個数）計算機

整数 N（1〜1,000,000）を入力すると、N と互いに素な 1〜N の整数の個数（オイラーのφ関数 φ(N)）を、答えだけでなく素因数分解と計算式つきで即時表示します。1〜100のφ(n)早見表も無料で見られます。