素数とは、1 とそれ自体の 2 つの因数を正確に持つ 1 より大きい整数です。素数はすべての整数の構成要素であり、すべての整数は素数の積として表現できます。

最初の 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

偶数の素数は 2 だけであることに注意してください。他のすべての偶数は 2 で割り切れます。

方法 1: トライアル部門

数値が素数かどうかをテストする最も簡単な方法は、平方根までの数値がそれを均等に割るかどうかをチェックすることです。

重要な洞察: n に √n より大きい係数がある場合、それに対応する √n より小さい係数もあります。したがって、√n までを確認するだけで済みます。

アルゴリズム：

  1. n < 2 の場合、素数ではない
  2. n = 2 の場合、素数
  3. n が偶数の場合 (2 を除く)、素数ではない
  4. 3 から √n までの奇数をすべてチェックします
  5. n を均等に割る場合は素数ではない
  6. それ以外の場合はプライム

例: 97 は素数ですか?

√97 ≈ 9.85 なので、9 までの素数を確認します: 2、3、5、7

  • 97 ÷ 2 = 48.5 (全体ではありません)
  • 97 ÷ 3 = 32.33... (全体ではありません)
  • 97 ÷ 5 = 19.4 (全体ではありません)
  • 97 ÷ 7 = 13.86 (全体ではありません)

約数が見つかりません — 97 は素数です。

例: 91 は素数ですか?

√91 ≈ 9.54、9 までチェック: 2、3、5、7

  • 91 ÷ 7 = 13 (整数!)

91 は素数ではありません — 91 = 7 × 13。

方法 2: エラトステネスのふるい

エラトステネスのふるいは、指定された制限までのすべての素数を検出します。これは高速かつエレガントで、紀元前 240 年頃にギリシャの数学者エラトステネスによって発明されました。

50 までのすべての素数を見つけるには:

  1. 2 ～ 50 の数字を書き出す
  2. 2 (最初の素数) から始めます。 2 の倍数 (4、6、8...) をすべて取り消し線で消します。
  3. 次のクロスのない数字に移動します。 3. 3 の倍数 (9、15、21...) を取り消します。
  4. 次のクロスを取り除きます: 5. 5 の倍数 (25、35...) を取り消します。
  5. 次のクロスを解除します: 7. 7 の倍数 (49...) をクロスアウトします。
  6. √50 ≈ 7.07 に到達したら終了
  7. 交差していない残りの数字はすべて素数です

最大 50 の素数: 2、3、5、7、11、13、17、19、23、29、31、37、41、43、47

最大 100 の素数: 完全なリスト

範囲 素数
1～10 2, 3, 5, 7
11～20 11, 13, 17, 19
21～30 23, 29
31–40 31, 37
41–50 41, 43, 47
51–60 53, 59
61–70 61, 67
71–80 71, 73, 79
81–90 83, 89
91–100 97

100 未満の素数は 25 個あります。

簡単な可分性テスト

完全な除算を行う前に、次のルールを確認してください。

で割り切れる もし...
2 最後の桁は偶数 (0、2、4、6、8)
3 3で割り切れる数字の合計
5 最後の桁は0または5です
7 単純なルールはありません - ただ分けるだけです
11 11 で割り切れる交互の数字の合計

例: 143 は素数ですか?

  • ✓でもありません
  • 1+4+3 = 8、3 では割り切れません ✓
  • 0 または 5 で終わらない ✓
  • √143 ≈ 11.96、11までチェック
  • 143 ÷ 7 = 20.43 ✓
  • 143 ÷ 11 = 13 — 割り切れます!

143 = 11 × 13。素数ではありません。

素数が重要な理由

暗号化: RSA 暗号化 (インターネット バンキング、HTTPS、および電子メールのセキュリティを保護するために使用されます) は、2 つの大きな素数を乗算するのは簡単ですが、結果を素数に因数分解するのは非常に難しいという事実に基づいています。

コンピューター サイエンス: ハッシュ テーブル、乱数ジェネレーター、チェックサムは素数のプロパティを使用します。

純粋な数学: 素数の分布は、数学における最も深い未解決の問題の 1 つであるリーマン予想です。

興味深い主な事実

  • 既知の最大の素数 (2024 年現在) は 4,100 万桁以上あります
  • 双子素数とは、2 異なる素数です (11 と 13、17 と 19、41 と 43)。
  • 素数は無限に存在します - 紀元前 300 年頃にユークリッドによって証明されました
  • ゴールドバッハ予想 (1742 年以降証明されていない): 2 を超えるすべての偶数は 2 つの素数の合計です

次を読む