素数と言う自然数は、まことに不思議な数字で無限に存在するのかどうかを証明したのはユークリッド（紀元前300年ごろの人）だと言います。
無限に素数は存在します。
ユークリッドの論法はこうです。
仮に素数を有限とします。
昇順に並べた素数の集合P（p1,p2,p3…pn）を考えます。
するとn番目の素数が、素数の最大値だと仮定できます。
Pの要素、つまり素数をすべて掛けて積を得たとしましょう。
Pの積をK＝p1・p2・p3…pnとします。
これは後で述べますが合成数ですね。
これに１を足す。
K+1 …①
①はPの要素である素数のいずれかで割ると必ず余りが１になって割り切れません。
するとK+1自体が素数でなければなりません。
だとするとおかしいですよね。
仮定ではp1～pnのn個しかない素数だったはずなのに、K+1も新たに素数だと言うのですから、これじゃあn+1個だ。
こんなことを続けていけば一個ずつ素数は増えていきますやん。
というわけで、最初の「素数は有限」という仮定が誤っていたのですよ。
「だから素数は無限に存在するんですよ」と、ユークリッドは言うたんです。
落語の「壷算」じゃないですけどね。
なかなか見事に「言いくるめられた」あたしです。
これって「背理法」じゃないの？
「背理法も立派な証明方法なんですよ」と、ユークリッドが言ったとか言わなかったとか。
数学の劣等生だったあたしは「はぁ、そうですか」としか言いようがありません。
素数を調べる場合に、さっき出てきた「合成数」という考え方が出てきます。
あたしは数学者ではないので、詳しいことはわからないけれど、自然数の集合を考えて、その中で１とその数以外の数を約数に持つ数を合成数というのだと習いました。
言い換えれば１とその数以外に約数を持たない数は素数ですね。
合成数の代表例は偶数がそうです。
そして素数はすべて奇数です。
気が付かなかったんだけど、二つ以上の素数の積は合成数だということ。
（それくらい気が付けよ、あんぽんたん！）
ある数字を素数に分解することを素因数分解と言うのでしたね。
素因数とはその分解された素数のことであり、合成数はすべて素因数に分解されるのです。
ユークリッドの少し後の人でエラトステネスというギリシャの科学者がいました。
アルキメデスの友人だった人です。
エラトステネスは素数を求めるのにある考え方を提案しました。
これを「エラトステネスの篩（ふるい）」と言います。
自然数は合成数と素数でできているということは、これまでのお話で理解できたと思います。
すると、合成数と素数をよりわける「篩」があれば、素数を求めることができますね。
その篩とはこういうことです。
簡単に「100までの自然数の中で素数はどんだけあるんだろう」という疑問に答えてみましょう。
100の平方根は10ですね。
10までの素数ならすぐ求まります。
1は素数ではないですから、2、3、5、7の四つです。
合成数の考えでは素数の倍数は合成数ですから、素数ではありえないので除いていきます（篩にかける）。
2、4、6…98
3、6、9…99
5、10、15…100
7、14、21…91
これらの合成数を篩い落とした残りが素数になってます。
2、3、5、7、11、13、17、19…97
ある自然数より小さい素数を求めるには、その自然数の平方根より小さい素数の倍数で合成数ができているはずだから、それらを除けば素数が求められるということをエラトステネスは考えついたのですね。
√N （N：自然数）≧素数
その素数の倍数集合（合成数集合）の補集合が素数の集合です。
無限に素数は存在します。
ユークリッドの論法はこうです。
仮に素数を有限とします。
昇順に並べた素数の集合P（p1,p2,p3…pn）を考えます。
するとn番目の素数が、素数の最大値だと仮定できます。
Pの要素、つまり素数をすべて掛けて積を得たとしましょう。
Pの積をK＝p1・p2・p3…pnとします。
これは後で述べますが合成数ですね。
これに１を足す。
K+1 …①
①はPの要素である素数のいずれかで割ると必ず余りが１になって割り切れません。
するとK+1自体が素数でなければなりません。
だとするとおかしいですよね。
仮定ではp1～pnのn個しかない素数だったはずなのに、K+1も新たに素数だと言うのですから、これじゃあn+1個だ。
こんなことを続けていけば一個ずつ素数は増えていきますやん。
というわけで、最初の「素数は有限」という仮定が誤っていたのですよ。
「だから素数は無限に存在するんですよ」と、ユークリッドは言うたんです。
落語の「壷算」じゃないですけどね。
なかなか見事に「言いくるめられた」あたしです。
これって「背理法」じゃないの？
「背理法も立派な証明方法なんですよ」と、ユークリッドが言ったとか言わなかったとか。
数学の劣等生だったあたしは「はぁ、そうですか」としか言いようがありません。
素数を調べる場合に、さっき出てきた「合成数」という考え方が出てきます。
あたしは数学者ではないので、詳しいことはわからないけれど、自然数の集合を考えて、その中で１とその数以外の数を約数に持つ数を合成数というのだと習いました。
言い換えれば１とその数以外に約数を持たない数は素数ですね。
合成数の代表例は偶数がそうです。
そして素数はすべて奇数です。
気が付かなかったんだけど、二つ以上の素数の積は合成数だということ。
（それくらい気が付けよ、あんぽんたん！）
ある数字を素数に分解することを素因数分解と言うのでしたね。
素因数とはその分解された素数のことであり、合成数はすべて素因数に分解されるのです。
ユークリッドの少し後の人でエラトステネスというギリシャの科学者がいました。
アルキメデスの友人だった人です。
エラトステネスは素数を求めるのにある考え方を提案しました。
これを「エラトステネスの篩（ふるい）」と言います。
自然数は合成数と素数でできているということは、これまでのお話で理解できたと思います。
すると、合成数と素数をよりわける「篩」があれば、素数を求めることができますね。
その篩とはこういうことです。
簡単に「100までの自然数の中で素数はどんだけあるんだろう」という疑問に答えてみましょう。
100の平方根は10ですね。
10までの素数ならすぐ求まります。
1は素数ではないですから、2、3、5、7の四つです。
合成数の考えでは素数の倍数は合成数ですから、素数ではありえないので除いていきます（篩にかける）。
2、4、6…98
3、6、9…99
5、10、15…100
7、14、21…91
これらの合成数を篩い落とした残りが素数になってます。
2、3、5、7、11、13、17、19…97
ある自然数より小さい素数を求めるには、その自然数の平方根より小さい素数の倍数で合成数ができているはずだから、それらを除けば素数が求められるということをエラトステネスは考えついたのですね。
√N （N：自然数）≧素数
その素数の倍数集合（合成数集合）の補集合が素数の集合です。
