エラトステネスの篩

この記事の所要時間: 29

エラトステネスの篩

エラトステネスの篩とは

古代ギリシャの数学者, エラトステネスが考案したとされる, 素数の判定法です.

決められた自然数 \(N\) 以下のすべての素数を求めることができます.

アルゴリズムの具体的な例(N=15 の場合)

15以下の素数を求めます.

  1. \(A\) を素数の候補の集合とします. はじめは, 2 ~ 15 のすべてが候補で, \(A=\{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15\}\) となります.
  2. 集合\(A\) の中で最小のもの 2 は素数です. \(B\) を素数であると判定済みの数の集合として, \(B=\{2\}\) とします. 2は素数と判定済み, 他の2の倍数は素数ではないので, \(A\)から削除します. すると, \(A=\{3, 5, 7, 9, 11, 13, 15\}\).
  3. 同様に, \(A\) の最小の数3を\(B\) にうつして, 3の倍数を\(A\)から削除します. \(A=\{5, 7, 11, 13\}\), \(B=\{2, 3\}\).
  4. \(A\) の最小の数は5で, \(\sqrt{15}=3.87\) よりも大きいので, この時点で\(A\)に残っている数はすべて素数となり, \(B\)にうつします. \(A=\{\}, B=\{2, 3, 5, 7, 11, 13\}\)

アルゴリズムの説明

素数の候補の集合 \(A\) の中で最小の数が素数になることは明らかです.

(\(\because\) もし素数でなければ, 自分より小さいある素数で割り切れるので, 先に\(A\)から削除されていなければならないので. )

そこで, \(A\) の最小の数を素数として, その数の倍数をすべて削除することをくり返します.

\(N\) 以下の素数を求めたい場合, \(A\) の最小の素数が \(\sqrt{N}\) を超えたとき\(A\)に残っている数は素数になります.

\(\sqrt{N}\) を超える素数\(p\)の倍数で, \(N\)以下のものは, \(p>\sqrt{N}\) より \(p^2>N\) なので, \(p\) よりも小さい素数で割り切れることになり, すべて既に削除されているからです.

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加