素数判定・素因数分解 計算ツール｜大きい数も対応、素数定理・RSA暗号・OEIS完全対応
任意の自然数について素数か合成数かを瞬時に判定し、素因数分解・約数一覧・前後の素数を同時算出します。素数はユークリッドが「無限に存在する」ことを証明した数学の基本粒子であり、RSA暗号・楕円曲線暗号・ハッシュ関数・乱数生成・誤り訂正符号など現代情報社会の安全基盤にも直結する概念です。中学入試の約数問題から、双子素数・メルセンヌ素数・フェルマー素数といった発展話題、Miller-Rabin判定法、素数定理 π(x) ~ x/ln(x) まで、日本数学会・OEIS・IPA情報処理推進機構・大学入試センターの公的資料に基づき詳解します。
素数 判定計算機
素数の定義と算術の基本定理
素数(prime number)とは、1より大きい自然数のうち、1とその数自身以外に正の約数を持たないものです。2は唯一の偶数の素数で、3以降の素数はすべて奇数です。1は素数にも合成数にも分類されません(現代数学の慣習)。
算術の基本定理(素因数分解の一意性)により、2以上のすべての自然数は、素数の積として一意的に表現できます(順序を除いて一意)。
n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ (pᵢ は素数、aᵢ は自然数)
この性質は整数論の出発点で、約数の個数公式 d(n) = (a₁+1)(a₂+1)...(aₖ+1)、約数の和 σ(n)、オイラーのφ関数、メビウス関数 μ(n) など、初等整数論のあらゆる関数の計算根拠になっています。ユークリッドは紀元前300年頃、素数が無限に存在することを背理法で証明し、数学史上最古の重要な証明の1つとされています。
100以下の素数表(25個)
1〜100の間には25個の素数があります。中学受験・高校数学Aの整数分野で覚えておくと便利です。
| 範囲 | 素数 | 個数 |
|---|---|---|
| 1〜10 | 2, 3, 5, 7 | 4個 |
| 11〜20 | 11, 13, 17, 19 | 4個 |
| 21〜30 | 23, 29 | 2個 |
| 31〜40 | 31, 37 | 2個 |
| 41〜50 | 41, 43, 47 | 3個 |
| 51〜60 | 53, 59 | 2個 |
| 61〜70 | 61, 67 | 2個 |
| 71〜80 | 71, 73, 79 | 3個 |
| 81〜90 | 83, 89 | 2個 |
| 91〜100 | 97 | 1個 |
| 合計 | — | 25個 |
1000以下は168個、10000以下は1229個、10万以下は9592個、100万以下は78,498個の素数があります(OEIS A000720「π(n)」)。
素数族の分類表
素数には特殊な性質を持つ「族(family)」がいくつも存在し、それぞれが数学史・情報科学で重要な役割を果たしています。
| 名称 | 定義 | 例 | OEIS |
|---|---|---|---|
| 双子素数 | 差が2の素数ペア (p, p+2) | (3,5)(5,7)(11,13)(17,19) | A001359 |
| いとこ素数 | 差が4の素数ペア | (3,7)(7,11)(13,17) | A023200 |
| セクシー素数 | 差が6の素数ペア | (5,11)(7,13)(11,17) | A023201 |
| 三つ子素数 | (p, p+2, p+6) or (p, p+4, p+6) | (5,7,11)(11,13,17) | A007529 |
| メルセンヌ素数 | 2ⁿ−1 の形の素数 | 3, 7, 31, 127, 8191, 131071 | A000668 |
| フェルマー素数 | 2^(2ⁿ)+1 の形の素数 | 3, 5, 17, 257, 65537 | A019434 |
| ソフィー・ジェルマン素数 | 2p+1 も素数となる素数 p | 2, 3, 5, 11, 23, 29, 41 | A005384 |
| 安全素数 | (p−1)/2 も素数となる素数 p | 5, 7, 11, 23, 47, 59 | A005385 |
| 回文素数 | 10進で回文になる素数 | 11, 101, 131, 151, 181 | A002385 |
| 逆順素数 | 10進の並びを逆にしても素数 | 13(→31)、17(→71)、37(→73) | A006567 |
2024年7月時点、既知の最大の素数は 2^136,279,841−1(41,024,320桁)のメルセンヌ素数(GIMPS 2024年発見)。世界的な分散計算プロジェクト GIMPS(Great Internet Mersenne Prime Search) が更新を続けています。
エラトステネスの篩(sieve of Eratosthenes)
N 以下のすべての素数を列挙する、紀元前3世紀のアルキメデスの同時代人・エラトステネス(Eratosthenes, 前276-前194)が考案したアルゴリズム。計算量 O(N log log N) で今も高速素数列挙の標準法です。
手順
- 2から N までの整数を並べる。
- 最小の未処理の数 p を素数とマークする(最初は p=2)。
- p の倍数(2p, 3p, ...)をすべて削除する。
- p² > N になるまで手順2-3を繰り返す。
- 残った数がすべて素数。
実装は数行のプログラムで書けます。日本情報オリンピック(JOI)や情報処理推進機構(IPA)の基本情報技術者試験でも頻出のアルゴリズムです。ビット圧縮による最適化(篩を2ビット×N/2に圧縮)や、線形時間版(Euler's sieve)、Segmented sieve(範囲分割で L1キャッシュ効率化)など多数の改良版が知られています。
素数判定法(試し割り・Miller-Rabin)
試し割り法(trial division)
2 から √n までの整数で順に割り、割り切れなければ素数と判定。計算量 O(√n)。小さい n には十分ですが、n が 10¹² を超えると実用的でなくなります。本ツールはこの方式で判定しています。
フェルマー小定理判定
フェルマー小定理「p が素数なら a^(p−1) ≡ 1 (mod p)」の逆を疑似判定に使う方法。ただし擬素数(Carmichael数 561=3·11·17 など)が存在するため単独では信頼できません。歴史的には最初の高速判定法の1つ。
Miller-Rabin判定法
強フェルマー判定の確率版。ランダムな a を k 個試すと誤判定確率 4⁻ᵏ 以下。k=20 で誤判定確率 10⁻¹² 未満。RSA公開鍵の候補生成で標準的に使用され、GPG・OpenSSL・OpenSSHの内部実装で採用されています。
AKS素数判定法
2002年にインドの3人組(Agrawal-Kayal-Saxena)が発表した、確定的多項式時間 O((log n)⁶) の判定アルゴリズム。理論的ブレークスルーで学術界にセンセーションを巻き起こしましたが、実装効率ではMiller-Rabinに劣ります。
素因数分解のアルゴリズム
素数判定と異なり、大きな数の素因数分解は計算量的に困難で、これがRSA暗号の安全性の根拠となっています。主要な因数分解アルゴリズム:
- 試し割り法 — O(√n)。小さい n や少数の小さな素因数を持つ n には最適。
- Pollard ρ法 — 期待計算量 O(n^(1/4))。中サイズ(10¹²〜10²⁰)の n に有効。
- 2次篩法(Quadratic Sieve) — 100桁台まで有効。1980年代の主流。
- 数体篩法(GNFS) — 現時点で最速。RSA-768(232桁)は2009年にGNFSで因数分解された。
- Shor'sアルゴリズム(量子計算) — 多項式時間で因数分解可能。量子コンピュータ実用化でRSAが破られる懸念の根拠。IBMなどが数百量子ビットのシステムを開発中。
素数定理と分布
N 以下の素数の個数を π(N) と表すと、Gauss・Legendreの予想を経て 1896 年に Hadamard と de la Vallée Poussin が独立に証明した素数定理(Prime Number Theorem, PNT)により、次の漸近式が成立します。
π(N) ~ N / ln(N) (N → ∞)
これは「N の付近では、log N 個に1個の割合で素数が現れる」ことを意味します。より精密には、対数積分 Li(N) = ∫₂ᴺ dt/ln(t) が更に良い近似を与えます。
素数の個数(検算)
| N | 実際のπ(N) | N/ln(N) | Li(N) |
|---|---|---|---|
| 10 | 4 | 4.34 | 6.17 |
| 100 | 25 | 21.7 | 30.13 |
| 1,000 | 168 | 144.8 | 177.6 |
| 10,000 | 1,229 | 1,086 | 1,246 |
| 100,000 | 9,592 | 8,686 | 9,630 |
| 1,000,000 | 78,498 | 72,382 | 78,628 |
| 10⁸ | 5,761,455 | 5,428,681 | 5,762,209 |
リーマン予想(未解決)が正しければ、素数分布のより厳密な誤差評価が可能になります。リーマン予想はミレニアム懸賞問題(賞金100万ドル)の1つで、日本数学会・AMS の重点研究テーマの1つとされています。
応用場面(RSA暗号・情報オリンピック)
🔐 RSA公開鍵暗号
2つの大きな素数 p, q を選び、n=pq を公開鍵とする方式。素因数分解の困難さが安全性の根拠。SSL/TLS・HTTPS・SSH・PGP など現代インターネットの通信暗号のバックボーン。日本の CRYPTREC(暗号技術検討会) がガイドライン公開。
楕円曲線暗号(ECC)
有限体上の楕円曲線を用いた暗号方式。素数位数の群を利用し、RSAより小さい鍵長で同等の安全性を実現。TLS・Bitcoin・EdDSAなどで採用。
ハッシュ関数・乱数生成
ハッシュ関数の内部定数、線形合同法乱数の周期最大化にも素数が使用されます。Mersenne Twister(MT19937)は 2^19937−1 のメルセンヌ素数を周期に持つ、擬似乱数の事実上の標準。
誤り訂正符号
Reed-Solomon符号(QRコード・CD・DVDで使用)は有限体 GF(2ⁿ) 上で構築され、生成多項式に既約多項式(素数の類似)を使います。NIST・IEEEの通信規格に組み込まれています。
日本情報オリンピック(JOI)
素数篩・素因数分解・オイラーのφ関数・素数分布の問題が頻出。整数論はアルゴリズム設計の基本科目で、JOI公式サイトに過去問と解説あり。
中学受験・高校入試の約数問題
約数の個数・約数の和は素因数分解が基礎。「180の約数はいくつ?」「12と18の最大公約数は?」といった中学入試問題は素因数分解による解法が定石。SAPIX・日能研などの主要塾でも学習単元として扱われます。
よくある間違い・注意点
- 1を素数に含める — 現代数学では1は素数ではありません。定義「1より大きい自然数で1と自身以外の正約数を持たない」で除外されます。1を素数とすると素因数分解の一意性が破れます。
- 0を素数と誤解 — 0は自然数の範疇外の場合が多く、素数の定義対象外です。日本の学習指導要領で「自然数=1以上」が標準ですが、集合論では0を含める場合もあります。
- 2を素数から除外 — 2は唯一の偶数の素数です。「偶数だから合成数」は誤り。素数の定義に「奇数」の条件はありません。
- 91を素数と判定 — 91 = 7 × 13 で合成数ですが、100前後で「素数っぽい」と誤答されやすい代表例。試し割りで √91 ≒ 9.5 まで割れば7で割り切れることが確認できます。
- √n までの試し割りを省略 — 素数判定では 2 から √n までの割り切れテストで十分。それ以上を試すのは無駄です(証明: n=ab なら min(a,b)≦√n)。
- フェルマー数が全て素数と誤解 — Fermat数 Fₙ = 2^(2ⁿ)+1 は F₀=3〜F₄=65537 まで素数ですが、F₅ = 4,294,967,297 = 641 × 6,700,417 で合成数と Euler が発見。以降 F₅〜F₃₂ はすべて合成数と判明。
- 大きな数の素数判定に試し割りを使う — n が10¹²を超えると試し割りは実用的でありません。Miller-Rabin・AKSなど高速判定法を使ってください。
学習指導要領・入試との対応
日本の学習指導要領における素数・素因数分解の扱いは以下の通りです。
- 小学校算数(第5学年) ― 約数・倍数・公約数・最小公倍数を扱う。素数の概念は明示されないが、素因数分解の下地となる。
- 中学校数学(第3学年) ― 学習指導要領上は「素数・素因数分解」が明示的に含まれる。因数分解の準備。
- 高等学校数学A「整数の性質」 ― 素数・素因数分解、最大公約数・最小公倍数、合同式、ユークリッド互除法、n進法の学習(選択単元)。大学入試共通テストでも出題される。
- 基本情報技術者・応用情報技術者(IPA) ― 素因数分解・RSA暗号・ハッシュ関数の理論的基礎として頻出。
- 日本情報オリンピック(JOI) ― 素数篩・オイラーのφ関数などアルゴリズム問題として頻出。
参考文献・公的資料
素数・整数論の学習と応用について、以下の公的機関・学会のリソースを参照してください。
- 文部科学省 高等学校学習指導要領(平成30年告示) ― 数学Aの「整数の性質」で素数・素因数分解・ユークリッド互除法の学習範囲を規定。
- 日本数学会 ― 数学各分野の日本語標準用語の準拠元。整数論分科会の学術資料。
- 大学入試センター(DNC) ― 共通テスト過去問と出題範囲。数学Aの整数分野は選択科目として扱われる。
- OEIS A000040(素数列) ― オンライン整数列大辞典の素数のエントリー。素数の一次データベースとして世界標準。双子素数・メルセンヌ素数などすべてのシリーズも網羅。
- Wolfram MathWorld ― Prime Number ― 素数に関する英語圏の総合リファレンス。素数定理・リーマン予想・素数判定法の厳密解説。
- American Mathematical Society (AMS) ― アメリカ数学会。整数論分野の学術論文リポジトリ。
- 情報処理推進機構 IPA / CRYPTREC(暗号技術検討会) ― RSA暗号・楕円曲線暗号など、日本政府の暗号技術ガイドライン。素数の暗号応用の実務指針。
- NIST FIPS 186-5 Digital Signature Standard ― 米国国立標準技術研究所のデジタル署名標準。RSA・DSA・ECDSAでの素数長要求。
- 日本情報オリンピック(JOI) ― 素数篩・整数論アルゴリズムを含む公式コンテストと過去問。
- GIMPS(Great Internet Mersenne Prime Search) ― メルセンヌ素数を分散計算で探索する世界プロジェクト。最新の最大素数記録の公式発信元。
よくある質問(FAQ)
1は素数ですか?
1は素数ではありません(現代数学の慣習)。素数の定義「1より大きい自然数で1と自身以外に正約数を持たない」に該当しません。1を素数とすると、算術の基本定理「素因数分解の一意性」が破れます(例:6=2×3=1×2×3=1×1×2×3...)。合成数でもなく「単数(unit)」に分類されます。
2は素数ですか?
2は素数です。約数は1と2のみ。唯一の偶数の素数で、以降の素数はすべて奇数です。「偶数=合成数」は誤りで、素数の定義に「奇数」の条件はありません。
素数はどれくらいの頻度で現れる?
素数定理により、N の付近では「約 ln(N) 個に1個」の割合で素数が現れます。N=100 なら約4.6個に1個、N=10,000 なら約9.2個に1個、N=10¹⁰ なら約23個に1個。大きい N ほど素数はまばらになりますが、無限に存在します(ユークリッドの証明)。
91は素数ですか?
91は素数ではありません(合成数)。91 = 7 × 13。100前後で「素数っぽい」と誤答されやすい代表例。試し割りで 2, 3, 5, 7 まで割ると 7 で割り切れます。他にも 51=3×17、57=3×19、77=7×11、87=3×29、91=7×13、93=3×31、95=5×19、119=7×17 など、「一見素数」の合成数に注意。
大きい数が素数か判定するには?
10¹² 以下なら試し割り法で十分。それ以上はMiller-Rabin確率的判定法を使うのが標準。誤判定確率 4⁻ᵏ(k=試行回数)で、k=20 なら 10⁻¹² 未満。RSA公開鍵生成でも標準採用。理論的に確定な判定が必要なら AKS 判定法。Python SymPy の isprime() は内部で BPSW + Miller-Rabin を使い、実用的に確実です。
双子素数は無限に存在しますか?
未解決問題(双子素数予想)です。差が2の素数ペア (p, p+2) が無限に存在するかは、Zhang Yitang(張益唐)が2013年に「差が7000万以下の素数ペアが無限」を証明する大突破がありましたが、「差が2」までは詰め切れていません。ミレニアム関連の重要未解決問題の1つ。
リーマン予想と素数の関係は?
リーマン予想は「リーマンゼータ関数 ζ(s) の非自明な零点の実部がすべて 1/2 に等しい」という予想。もし正しければ、素数の分布に関する漸近誤差がより精密に評価できます。現在ミレニアム懸賞問題(賞金100万ドル)の1つ。日本数学会・AMS の重要研究テーマ。
RSA暗号はなぜ安全なのですか?
2つの大きな素数 p, q の積 n=pq を公開しますが、n から p, q を復元(素因数分解)することが計算的に困難であるためです。2048bit RSAの場合、現在の古典コンピュータでは実質的に不可能。ただし量子コンピュータ(Shorのアルゴリズム)が実用化されれば脅威となるため、耐量子暗号への移行が進んでいます(NIST の Post-Quantum Cryptography 標準化)。
素因数分解を高速に行うには?
小さい n(10⁶ 以下)なら試し割りで即答。中サイズ(10¹²〜10²⁰)なら Pollard ρ 法、大サイズ(10⁵⁰以上)なら 2次篩・数体篩法(GNFS)を使います。Python なら SymPy の factorint()、Wolfram Mathematica なら FactorInteger[] が実装済み。Msieveや YAFU といったオープンソース実装もあります。
約数の個数はどう計算する?
n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ と素因数分解できるとき、約数の個数は d(n) = (a₁+1)(a₂+1)...(aₖ+1)。例:12 = 2² × 3 → (2+1)(1+1) = 6 個。12の約数は1,2,3,4,6,12の6個で一致。中学入試の頻出問題の解法根拠です。
メルセンヌ素数と完全数の関係は?
2ⁿ−1 が素数なら 2^(n−1) × (2ⁿ−1) は偶数の完全数(自分自身以外の約数の和が自分自身)。例:2²−1=3で6=1+2+3、2³−1=7で28=1+2+4+7+14。既知の完全数はすべて偶数で、奇数の完全数の存在は数論上の未解決問題です。
PythonやExcelで素数判定するには?
Python は from sympy import isprime, factorint; isprime(n); factorint(n)。Excel には直接の関数はありませんが、範囲内の素数判定なら =IF(SUMPRODUCT(--(MOD(N,ROW(INDIRECT("2:"&INT(SQRT(N)))))=0))=0,"素数","合成数") のようなUDFで対応可能。Google スプレッドシートでも同様、または App Script で isPrime 関数を定義できます。