数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

エラトステネスの篩(ふるい)


スポンサードリンク

エラトステネスの篩とは

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

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

 

アルゴリズム

N以下の素数を求めたいとします.

  1. 素数の候補の集合の初期状態としてA=\{2, 3, \ldots, N\} とします.また,素数であると判定された数の集合をB=\{\}とします.
  2. 素数の候補の集合Aの要素で最小のものをaとします.
  • a ^ 2\leqq Nのとき:aBに追加し,素数候補の集合Aからaの倍数を削除します.a ^ 2 > Nが満たされるまで 2. の手順を繰り返します.
  • a ^ 2 > Nのとき:現在Aに残っている数はすべて素数であると判定し,すべての要素をBに移して終了となります.

アルゴリズムの具体的な例(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で,  5^2=25 > 15 なので, この時点で 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 よりも小さい素数で割り切れることになり, すべて既に削除されているからです.