福西です。
M君は「公倍数」と「公約数」についてレクチャーをしてくれました。
（M君の板書）
Eさんは「最大公倍数」と「最大公約数」、「エラトステネスのふるい」について説明をしてくれました。
それを聞いて、私自身も教わるところがありました。「1を素数とせず、また2を素数とするのはなぜか？」についてです。私自身はこれまで「素数の定義が１と自分自身で割り切れる数だから」ぐらいにしか説明できなかったのですが、それを以下のエラトステネスのふるいの実行条件から自然と出てくるのだと思うことで、より納得できました。
Eさん
「30までの自然数について、エラトステネスのふるいを説明します。
自然数の小さな数から順に、（まだ残っている）数を１つ選びます。
そして選んだ数は残して、その倍数を（残した数以外）を消します。
ただし上の方法だと、１を選ぶとその倍数として１以外のすべてが消えてしまうので、1は最初から除外しておきます。
２を選んで、４、６、８…と4以上の2の倍数を消します。
3を選んで、6以上の3の倍数を消します。
4はすでに消えています。
5を選んで、10以上の5の倍数を消します。
6はすでに消えています。
7を選びますが、ここで7>√30なので、ここでふるいは終了です。
残った数（選んだ数を含む）は、2、3、5、7、11、13、17、23、29です。
結局、2以外の素数を見つけるには、奇数の中から探すことになります」
終了条件も説明してくれていたのが良かったです。
「7>√30なので」に対するEさんの説明を、以下に補足しながら書いておきます。
考える数が1～nまでの自然数の場合
n=abとできるとし、ふるいにかけるために選ぶ数をaとする。
n=√n・√n。
a>√nとなった時点で、b<√nなので、
aについてふるいをかける時には、すでにbについてふるいを実行した後になる。
よってふるいをかける必要はなく、ここで終了する。
エラトステネスのふるいは、素数を見つける一種のアルゴリズムです。
授業ではそれを100まで拡張して実行しました。
また公倍数・公約数の話から、素因数分解、ユークリッドの互除法にも触れました。互除法もまたアルゴリズムです。これについては来週も見ます。
来週の範囲は、p42～49です。