今回は問題の解説ではなく、ちょっとした知識の講座です。
自然数を２つのチームに分類するお話。片方は素数（そすう）チーム、もう片方は合成数（ごうせいすう）チームです。


素数は、１とその数自身以外に約数を持たない自然数のことで、素数でない自然数は合成数です。
素数の方は有名だと思いますが、合成数の方はあまり名前が知られていないかも知れません。反対の関係の言葉として、両方覚えておいてくださいね。
あっ、それから１は素数でも合成数でもありません。１は今回のお話のレフェリーみたいな数で、まったく中立の立場です。
だから正確に言えば、自然数は〈１〉か〈素数〉か〈合成数〉ということになりますね。

え？　０ですか？
０は整数には含（ふく）まれるけど、自然数には含まれないのね。今回の話は自然数の範囲で考えるから、０のことは気にしないでください。それから、０より小さいマイナスの整数も、算数では想定しないことになっています。

※整数と自然数の違い
整数…０と、０に１ずつ加えていくことで得られる数。算数では想定しないが０から１ずつ引いていくマイナスの整数もある。
自然数…整数のうち、０とマイナスの整数を除いた数。１以上の整数。数を数えるときに使う数という説明もできます。
つまり、算数では０を含めると整数、含めなければ自然数ということです。

さて今回のタイトルはエラトステネスのふるいです。
エラトステネスは紀元前の学者で、地球の大きさを測定するなど、第二のプラトンと呼ばれるほど優秀だった人ですが　参考文献wikipedia　彼は、自然数を素数と合成数に分けていく方法として〈エラトステネスのふるい〉を考案しました。
ふるい　というのは左の写真のような道具のことで、穴の大きさによって、それより小さな物質を ふるい落とすためのものです。
なぜそんな名まえがついているのか、次の説明を読みながら考えてくださいね。


それではエラトステネスのふるいによって、100以下の自然数を素数と合成数に分けてみます。
100以下の自然数を順に書き並べた下の図を見ながらお読みください。

手順Ａ
素数ではない１を消す（■色）　※消した整数（素数ではない整数。合成数）はカラーで表示しています

手順Ｂ
素数の２を残し、素数ではない〈２以外の２の倍数〉をすべて消す（■色）

手順Ｃ
素数の３を残し、素数ではない〈３以外の３の倍数〉をすべて消す（■色）

手順Ｄ
素数の５を残し、素数ではない〈５以外の５の倍数〉をすべて消す（■色）

手順Ｅ
素数の７を残し、素数ではない〈７以外の７の倍数〉をすべて消す（■色）

100までの ふるい はここで分類作業終了です。すべての数が素数と合成数に分かれました。

もし、もっと広い自然数の範囲で ふるい を実行するなら
手順Ｆ
素数の11を残し、11以外の11の倍数をすべて消す
手順Ｇ
素数の13を残し、13以外の13の倍数をすべて消す
………というように続きます。

さて、この作業が ふるい と言われる理由はおわかりになったでしょうか？

素数２を残して２の倍数を消し、素数３を残して３の倍数を消し、
素数５を残して５の倍数を消し、…
こうした作業によって素数だけが ふるい の上に残され、素数ではない数（合成数）が ふるい の穴からふるい落とされていく…。そういうイメージですね。
上の図で白くなっているところが素数、色のついているところが１を除いて合成数です。
なかなか面白いでしょう？

さて、いまの100以下の範囲での ふるい では、７を残して７の倍数（49、77、91）を消したとき、分類作業が終了と書きました。なぜそこで終了になるか 理由はわかりますか？

７の次に小さい素数は11ですよね？
もちろん11は素数として残っていますが、それ以外の11の倍数は、22が２の倍数のときに消え、33が３の倍数のときに消え、………
というように、すでにすべてが消えているからです。
つまり、11×□という11の倍数で、□が11より小さいものは残っていません。もし□を11にすると 11×11＝121 だから、それは表の範囲を超えています。
という理由で、７の倍数を消した時点で操作終了ということになるのです。

＊＊＊
エラトステネスのふるい　いかがでしたでしょうか？
じつは素数という数の世界には、まだまだ多くの謎が隠されていましてね。たとえば、ある大きな自然数（例えば573491273）が素数かどうかを簡単に調べる方法は、現在までの科学では発見されていません。
そうした方法（大きな数の素数判定）が果たして存在するのか、しないのか？それすらもわかっていません。もしみなさんがいつか発見したら、フィールズ賞受賞は間違いありませんよ。
※数学にはノーベル賞がありません。かわりにフィールズ賞が数学での最高栄誉です。

まぁ、算数ではあまり大きな数の素数判定は必要ないと思いますが、100まで（できれば200まで）の自然数が素数かどうかは、あまり時間をかけずに判断できると便利ですね。何回か ふるい を実行すれば、素数かどうかを覚えてしまう人も多いと思います。

じゃあ今回の講座、これにておしまいです。