エラトステネスの篩(フルイ)〜100までの自然数の場合〜
ギリシャの学者エラトステネスは、地球の大きさを測った偉人。
1を除く素数を並べる。
素数を見出すフルイにかける。
2の倍数を消す。素数の2はとっておく。
3の倍数を消す。素数の3はとっておく。
5の倍数を消す。素数の5はとっておく。
7の倍数を消す。素数の7はとっておく。
これだけで、100までの素数は見出すことができる。
100までの素数を見つけるのに、
4つの素数 2、3、5、7の倍数だけをふるいにかけた。
なぜ、それだけでいいのか?