エラトステネスの篩とは
素数を見つけ出すアルゴリズム。
「その数の平方根より小さい素数の倍数を消せば、残った数が素数である」という考え方に従って素数を探す。
フローチャート
100以下の素数を全て求める場合、以下のアルゴリズムとなる。
素数かどうか確かめたい数を代入する配列を、arrayとする。
iはarrayの添字。
kは倍数を取り除く素数。(kが２なら２の倍数を取り除き、kが３なら３の倍数を取り除く)
変数arrayに0~100までの全ての添字に値1が対応した状態でスタートし、素数でない添字には0を代入していく。
素数でない添字に0を代入する処理が終わった段階で要素が1の添字が素数となる。
