素数の定義

1とそれ自身以外に約数をもたない自然数を、素数という。素数でないものは、（素数のかけ算で表されるので）合成数という。ただし、１は素数でも合成数でもない。（数学B p161 数研出版 2007)

背景

素数は、数学者にとって難敵。なんだか、すっきりしない世界なのです。たとえば:
- 素数は、無限に多く存在する。（またまた）「ユークリッドの素数定理」
- いいかえると、素数は有限個ではない。証明は背理法 [証明例]
- 素数には「世界記録」、つまり現時点で最大の素数がある。でも、上の定理から、もっと大きい素数があるはずだ。
新しい「素数」を見つける、うまいやり方は、あるのだろうか。
素数の分布には、何か法則があるのだろうか。
ある数を（素数の掛け算に分解する）素因数分解する、うまいやり方は、あるのだろうか。

「素数は有限個、その個数をn個、最大の素数をPnと仮定する」（この仮定から矛盾が導かれることを示す作戦）
Pnより小さい素数(n-1個）をすべてかけあわせた合成数をQとする。
ここで、Q+1を考える。Q+1は、P1-Pnで割ると余りが１になり、割り切れない。
つまり、「素数の個数はn+1, 最大の素数はQ+1」が導かれる。これは仮定と矛盾する。
したがって、素数は有限個ではない。

テーマ

「Ｎより小さい素数をすべてあげなさい」

たとえば、Nが20のときは、2, 3, 5, 7, 11, 13, 17, 19

もちろん：上ができれば（Ｎより小さい素数が全てわかっているのだから）、Ｎが素数かどうかは判定できる。
- たとえば：ＮがＮより小さい素数で割れるかどうかを確かめる。割れれば合成数。全ての素数で割れないのなら、新素数！（もっと、うまいやり方はないのだろうか）

今回もまず、皆さん自身で、考えてみてください。
- 小さい数については、素数かどうかをすぐに判定できるけど。。（7は素数とわかる。でも、123457なんか無理でしょう）
たとえば10より小さい素数をすべてあげなさい、という問題から、だんだんＮを大きくしていきながら、自分はどうやっているんだろうと考えて、手続きを考えてください。さらに、Ｃプログラムにするとしたら、と手続きを考えてください。
各問題にタイマー機能がついています。できるだけ速く、間違えないよう、遊んでください。
先輩たちが作成した環境を利用します。コメントを残してあげてください。

今日の活動

10まで、30まで、50までとやってみて、自分がどうやっているのか、手続きをまとめてください。
- 自分の方法に名前をつけよう。アルゴリズムとして整理しよう。
- みんなの例を確認してみよう。
自分の方法をプログラムしよう。
課題、来週へ