前回まででエラトステネスの篩を使って100までの自然数の中から、２の倍数、3の倍数、5の倍数、7の倍数を消去して素数を求めました。
え？11の倍数は消えてないよ？
では11の倍数を見てみましょう。
11×２、11×３、11×５、11×７
はすでに消えています。次の素数は11ですが
11×11＝121
は100を超えているので消す必要はありません。このように100までの素数を求めるときは√100=10以下の自然数について検証すれば十分です。
少し一般化しましょう。
自然数nにおいて
n=pq ただしp,qは素数
とします。
このとき
p>√n かつ q>√nとすると
n = pq >√n√n=n
となり n>n と矛盾します。
したがって p<=n または q<=n
でなければならない。
100までの素数では
n = 100であるから、p <= 10、q <= 10
10以下の素数を検討するだけで十分です。
