素数計算機

素数計算機 - 素数の合計・個数・検索

🔢 素数の合計を計算し、範囲内の素数を見つけ、数が素数かどうかを判定し、 N番目の素数を求めます。可視化付きの高速「エラトステネスのふるい」アルゴリズム。

素数とは？

素数は、1より大きい自然数で、2つの約数（1と自分自身）だけを持つ数です。 言い換えると、2つのより小さい自然数の積として表すことができない数です。

最初の25個の素数

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

素数かどうかを確認する方法

方法1 - 試し割り：

• nが2から√nまでのいずれかで割り切れるかを確認する
• 割り切れれば合成数（素数ではない）
• 割り切れなければ素数

例：17は素数？

• √17 ≈ 4.12 なので、2・3・4で割り切れるかを確認
• 17 ÷ 2 = 8.5（割り切れない）
• 17 ÷ 3 = 5.67（割り切れない）
• 17 ÷ 4 = 4.25（割り切れない）
• 結果：17は素数！

エラトステネスのふるい

nまでのすべての素数を見つける古典的なアルゴリズム：

• ステップ1：2からnまでの数をすべて並べる
• ステップ2：2を素数として、2の倍数をすべて消す
• ステップ3：次の消されていない数（3）を素数としてマークする
• ステップ4：その素数の倍数をすべて消す
• ステップ5：√nまで繰り返す
• 結果：消されなかった数が素数

素数の合計

最初のn個の素数の合計：

• 最初の10個：2+3+5+7+11+13+17+19+23+29 = 129
• 最初の100個：合計 = 24,133
• 最初の1000個：合計 = 3,682,913

nまでの素数の合計：

• 10まで：2+3+5+7 = 17
• 100まで：合計 = 1,060
• 1000まで：合計 = 76,127

素数定理

n未満の素数の個数は、おおよそ n/ln(n)：

• 100まで：~25個（実際：25個）
• 1,000まで：~145個（実際：168個）
• 10,000まで：~1,086個（実際：1,229個）
• 100,000まで：~8,686個（実際：9,592個）

素数の種類

双子素数：差が2の素数の組

• (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)...

メルセンヌ素数：pが素数のとき 2ᵖ - 1 の形

• 2² - 1 = 3
• 2³ - 1 = 7
• 2⁵ - 1 = 31
• 2⁷ - 1 = 127
• 既知最大の素数はメルセンヌ型（約2,480万桁）

ソフィー・ジェルマン素数：pが素数で、2p+1も素数

• 2 (2×2+1 = 5), 3 (2×3+1 = 7), 5 (2×5+1 = 11), 11, 23, 29...

フェルマー素数：2^(2ⁿ) + 1 の形

• F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, F₄ = 65,537
• 既知のフェルマー素数は5つのみ

素数の応用

暗号（RSA）：

• 大きな数の素因数分解が難しいことを利用
• 数百桁の大きな素数を2つ使う
• オンラインバンキング、メール、Webサイトなどを保護

ハッシュテーブル：

• サイズを素数にすると衝突を減らせる
• データベースやキャッシュで利用

乱数生成：

• 素数はより良い疑似乱数列に役立つ
• シミュレーションやゲームで利用

面白い素数の事実

• 無限性：ユークリッド（紀元前300年頃）により素数は無限にあることが証明された
• ギャップ：連続する素数の間隔は任意に大きくできる
• ゴールドバッハ予想：2より大きいすべての偶数は2つの素数の和（未解決）
• リーマン予想：素数分布に関する懸賞問題
• 素数の間隔：連続する素数の差は一般に大きくなる
• 確率：ランダムなnが素数である確率は約1/ln(n)

素数の記録

• 既知最大の素数：2^82,589,933 - 1（2018年、24,862,048桁）
• 最大の双子素数：2,996,863,034,895 × 2^1,290,000 ± 1
• 計算：GIMPS（Great Internet Mersenne Prime Search）分散プロジェクト

よくある誤解

• 1は素数ではない：現代の定義では約数が2つ必要
• 奇数がすべて素数ではない：9, 15, 21, 25... は合成数
• すべての素数を生む公式：簡単な万能公式は存在しない
• 素数に規則性がある：予測可能なパターンは見つかっていない

💡 プロのヒント：大きな数が素数かどうかを調べるときは、平方根まで割り切れるかを確認すれば十分です。 例えば997が素数かどうかは √997 ≈ 31.6 なので、2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 を試せばOKです。 どれでも割り切れなければ素数です。さらに（2と3を除けば）素数はすべて 6k±1 の形であるため、探索を高速化できます。