- 361 名前：１３２人目の素数さん mailto:sage [2022/09/21(水) 20:01:21.76 ID:uBdCTt1j.net]
- >>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…となる。
