高校数学の質問スレ Part421

高校数学の質問スレ Part421 at MATH

354:１３２人目の素数さん
22/09/21 20:01:21.76 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…となる。

次ページ

続きを表示

1を表示