■素数定理とエラトステネスのふるい(その7)
(その2)において,2〜99の整数から,2の倍数,3の倍数,5の倍数,・・・をふるい落としてみた.その手順は(p以外の)pの倍数を順次ふるい落とすというものであった.
===================================
p=11のとき,ふるい落とされるものがなくなったが,これは11^2>100なので,これで100以下の素数はすべて求められたことになる.
もし2から1000までのすべての数字を書き出すところから始めた場合,
1000以下の素数をすべて求められたことになるのには,
√1000=31.6
すなわち,2〜1000の整数から,2の倍数,3の倍数,5の倍数,・・・をふるい落としていって,31を残しその他の31の倍数を消せばすべての作業が終了したことになる.
===================================