>>347
(2)エラトステネスの篩
1から整数を並べた表を用意する。
1は素数ではないので消す。
2は素数なので残す。4以降の2の倍数は全て消す。
3は素数なので残す。6以降の3の倍数は全て消す。
4は消えている。
5は残っているので素数であるので残す。10以降の5の倍数を全て消す。
6は消えている。
…これを繰り返すと素数のみが表に残る。

素数pに関する操作終了時にp²までに残っている整数は素数である。なぜならばp²以下の合成数はp以下の素因数を必ず持つからである。

例えばp=7とすると
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47…となる。