エラトステネスの篩

この記事の所要時間: 23

エラトステネスの篩

エラトステネスの篩とは

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

決められた自然数 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
  • このエントリーをはてなブックマークに追加