エラトステネスの篩
指定された整数X以下ののすべての素数をみつけるためのアルゴリズム
ある配列があるとする
1番目をfalseにする2番目以降を全部trueにする
配列リストの先頭から走査して次のtrueをみつける そのtrueの添字を素数リストに加える。その後pの2乗以上のpの倍数番目をfalseに設定 これを繰り返し走査している要素の添字がxの平方根になるまで続ける 最後までtrueだった要素の添字を素数リストに追加したら終了
ある約数の素数を探すときにその約数自身の割り切れる一番近い数字で割ったものが素数になる
順番にみていくときにその素数以外で割り切れるものを除外していく
これを繰り返す