トリビアクイズ　〜数論編　2〜

ヒント選択式のため、ヒントはありません。

解説正解は「97」です。

エラストテネスのふるいでは素因数が2つ以上ある数は消去されています。数は素因数の積で表されるため、素因数は元の数より小さいはずです。

問題では、97の倍数に関して、97*97=9409、97*101=9797、97*103=9991が消去されます。
次は101ですが、101*ｍ(ｍは100以下の数)は既にありません。ｍの倍数の時点で消去されているからです。
すると、次は101*101=10201ですが、これだと10000より大きくなります。以降103、107、109、……、9973も同じです。
つまり、25個の素数(2〜97)が出れば、残りの素数(101〜9973)は倍数を調べる必要はありません。ちなみに101〜9973で素数は1204個(！)ありました。

エラストテネスのふるいは1〜ｎの数から素数を見つけたいとき、√ｎ以下の数まで倍数を調べる必要があります。
問題ではｎ=10000なので、√10000=100で実質100の倍数まで調べる必要があります。しかし、98と100は2の倍数、99は3の倍数で消えるので、結局は97の倍数まで調べればいいことになります。
--------------------------------------------------
エラストテネスのふるい、自分もやってみました。表計算ソフトがあれば、多少面倒ですが、すぐに出来ます。
素数1229個のデータも自分で作りました。
最初は手書きだったけど時間食ったし間違えてたし。