01
素数（Prime Number）とは？
素数とは、1と自分自身以外に約数を持たない、1より大きい自然数のことです。2, 3, 5, 7, 11, 13... などが素数であり、2を除くすべての素数は奇数です。素数は数学の基本的な構成要素であり、「数の原子」と呼ばれています。
素数計算機
素数判定 · 素因数分解 · 素数生成
詳しく見る
02
エラトステネスのふるい
紀元前240年頃、ギリシャの数学者エラトステネスが考案した素数を見つけるアルゴリズムです。2から始めて各素数の倍数を消していくことで、効率的に素数を見つけます。
03
双子素数
差が2である素数のペアを双子素数といいます。(3,5), (5,7), (11,13), (17,19) などがあり、双子素数が無限に存在するかどうかは、いまだ未解決の問題です。
04
素数の活用
• RSA暗号：大きな素数の掛け算は簡単だが、素因数分解は困難であることを利用 • ハッシュ関数：素数を用いてハッシュテーブルのサイズを決定 • 乱数生成：素数を利用した擬似乱数の生成 • 周期の計算：セミの生命周期が素数の年数である理由
05
素数の定義と歴史
素数（Prime Number）は、1と自分自身以外に約数を持たない、1より大きい自然数です。最小の素数は2であり、唯一の偶数の素数です。2, 3, 5, 7, 11, 13, 17, 19, 23, 29... と続いていきます。古代ギリシャの数学者ユークリッドは紀元前300年頃に「素数は無限に存在する」ことを証明しました。素数は数学において非常に重要な役割を果たし、「数の原子（atoms of numbers）」と呼ばれています。算術の基本定理（Fundamental Theorem of Arithmetic）によれば、1より大きいすべての自然数は素数の積として一意に表されます。例えば60 = 2² × 3 × 5、360 = 2³ × 3² × 5です。これは、すべての物質が原子から成り立っているように、すべての数が素数から成り立っていることを意味します。
06
素数判定アルゴリズム
ある数nが素数かどうかを判定する最も単純な方法は、2からn-1までのすべての数で割ってみることですが、これは非常に非効率的です。改善された方法は、2から√nまでだけを確認することです。なぜなら、n = a × bのとき、a ≤ √nまたはb ≤ √nが必ず成り立つからです。例えば101が素数かどうかを確認するには、√101 ≈ 10.05なので、2, 3, 5, 7だけを確認すればよいのです。より効率的なミラー・ラビン（Miller-Rabin）の確率的素数判定法は、非常に大きな数も高速に判定できます。AKS素数判定法は、2002年に発見された最初の多項式時間の決定的アルゴリズムです。現代の暗号学では数百桁の素数を扱うため、効率的な素数判定が非常に重要です。
07
エラトステネスのふるい：素数生成アルゴリズム
エラトステネスのふるい（Sieve of Eratosthenes）は、紀元前240年頃にギリシャの数学者エラトステネスが考案した素数を見つけるアルゴリズムです。手順は次のとおりです：① 2からnまでのすべての数を並べます。② 2は素数なので印を付け、2の倍数（4, 6, 8, 10...）をすべて消します。③ 次の消されていない数3は素数なので印を付け、3の倍数（6, 9, 12, 15...）をすべて消します。④ 次の消されていない数5は素数なので印を付け、5の倍数をすべて消します。⑤ この過程を√nまで繰り返します。⑥ 残ったすべての数が素数です。例えば30までの素数を見つけると：2, 3, 5, 7, 11, 13, 17, 19, 23, 29です。このアルゴリズムの時間計算量はO(n log log n)で非常に効率的です。100万以下のすべての素数を数秒以内に見つけることができます。
08
素因数分解の原理と応用
素因数分解（Prime Factorization）とは、ある数を素数の積として表すことです。算術の基本定理により、1より大きいすべての自然数は一意の素因数分解を持ちます。素因数分解の方法：① 最小の素数2から始めて、割り切れるかどうかを確認します。② 割り切れる場合は2で割り続けます。③ これ以上2で割り切れなくなったら、次の素数3, 5, 7...で試します。④ 商が1になるまで繰り返します。例：360を素因数分解すると、360 ÷ 2 = 180、180 ÷ 2 = 90、90 ÷ 2 = 45、45 ÷ 3 = 15、15 ÷ 3 = 5、5 ÷ 5 = 1。したがって360 = 2³ × 3² × 5です。素因数分解の活用：最大公約数と最小公倍数の計算、分数の約分、RSA暗号の安全性の基盤。大きな数の素因数分解が難しいという点が、現代暗号学の核心です。
09
双子素数とゴールドバッハ予想
双子素数（Twin Primes）は、差が2である素数のペアです。(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)... などがあります。双子素数予想（Twin Prime Conjecture）は「双子素数が無限に存在する」という主張ですが、いまだ証明されていない数学の未解決問題の一つです。2013年、張益唐（Yitang Zhang）は差が7000万以下の素数のペアが無限に存在することを証明し、その後の共同研究によってこの間隔を246まで縮めました。ゴールドバッハ予想（Goldbach Conjecture）は「2より大きいすべての偶数は2つの素数の和で表せる」という主張です。例：4=2+2、6=3+3、8=3+5、10=3+7=5+5、100=3+97=11+89。1742年に提示されましたが、依然として証明されていません。コンピュータによって4×10¹⁸まで検証されています。
10
RSA暗号と素数の実用的な応用
RSA暗号はインターネットセキュリティの中核技術であり、大きな素数の掛け算は簡単だが素因数分解は困難であるという数学的性質を利用します。RSA鍵生成の過程：① 2つの大きな素数p, qを選びます（それぞれ1024ビット以上）。② n = p × qを計算します（公開鍵の一部）。③ φ(n) = (p-1)(q-1)を計算します。④ φ(n)と互いに素な公開指数eを選びます（通常は65537）。⑤ e × d ≡ 1 (mod φ(n))を満たす秘密指数dを計算します。公開鍵は(n, e)、秘密鍵は(n, d)です。暗号化：C = M^e mod n、復号：M = C^d mod n。nを素因数分解してpとqを求めれば秘密鍵dを計算できますが、数百桁の数の素因数分解は現在のコンピュータでも実質的に不可能です（数百万年かかる）。素数の他の応用：ハッシュテーブルのサイズを素数に設定すると衝突が減少、セミの13年・17年の生命周期は捕食者と周期が重ならないように進化したもの、音楽のリズムパターンでの素数拍子の使用。
よくある質問
素数はどこまで判定できますか？
このツールは1から10,000,000までの数値について素数判定と素因数分解に対応しており、素数生成と双子素数の検索は2〜100,000の範囲で動作します。
素数が暗号に使われる理由は何ですか？
2つの大きな素数を掛け合わせるのは簡単ですが、その積を再び素因数分解するのは非常に困難です。RSA暗号はまさにこの非対称性を利用してインターネット通信を保護します。