エラトステネスの篩
素朴な素数列挙アルゴリズム
最初に$ 2から$ nまでの自然数をリストに格納しておき、既知の素数で割り切れたものを全てリストから削除していく方法 リストの数を小さい値から順に調べていくため、上手くいくようになっている
12 までの素数列挙をする場合
リストに [2,3,4,5,6,7,8,9,10,11,12]をセット
以下で p の倍数と言った場合は p 自身は除くことに注意
リストから 2 の倍数を削除して [2,3,5,7,9,11] になる
リストから 3 の倍数を削除して [2,3,5,7,11] になる
リストから 5 の倍数を削除して [2,3,5,7,11] になる
リストから 7 の倍数を削除して [2,3,5,7,11] になる
リストから 11 の倍数を削除して [2,3,5,7,11] になる
リストの末尾に来たので終了