素数判定アルゴリズム〜エラトステネスの篩に関する疑問〜

今日は数学の話？アルゴリズムの話？どっちやろ。まいっか。
某大学で演習講師をやっているのだが、今日の素数判定プログラム課題にあったヒントにちょっと疑問があったので、
今日はそんな話。中身は数学かも。

さて、ヒントとしてエラトステネスの篩が書いてあった訳だが・・・・って、素数ってのは説明不要だよな。いいよな。
でも、いたからな、素数って何ですか？って学生が。。。
念のため書いておくと、１と自身のみ割り切れる数のことを素数という。
で、話を戻して、エラトステネスの篩の終了条件に関して、次のようなことが書いてあった。

$x$ が素数であるかどうかは $\frac{x}{2}$ までの数で割り切れるかどうかを調べればよい。

あれ？？？ $\sqrt{x}$ じゃなかったっけ？？でもあってそうだなぁ。
実際これでも大丈夫なんですね。

さて、xが素数であるかどうかを調べるときに、 $\frac{x}{2}$ まで、または $\sqrt{x}$ まで調べれば良いのはなんででしょう。アルゴリズムは知ってるが、これに答えられない人は結構いそう。
そんなに難しくありませんので、ちょっとやってみましょう。

xが素数でない（合成数）の場合x=pqとなる２以上の自然数p,qが存在する。p=qなら $\sqrt{x}=p$ なので、 $\sqrt{x}$ まで調べれば良いことになる。 $p\ne q$ のときpp^2] (なぜか改行しないとうまく処理されない。バグだねこれ。）
である。両辺平方根をとれば $\sqrt{x}>p$ となる。これは $\sqrt{x}$ 以下の自然数で割り切れることを意味しているため、 $\sqrt{x}$ まで調べれば十分である。

$\frac{x}{2}$ も同じようにやれば良い。xが偶数の場合2で割り切れるため素数でない。そこでxが奇数のとき成立するかを確認すれば良い。さっきと同じように x=pqと書けるとすると、xは奇数だからp,q>2である。従ってx>2p, x>2qであるので、 $\frac{x}{2}>p,q$ となる。なので、 $\frac{x}{2}$ まで調べれば十分ということになる。

とまぁ、こんな感じ。いやー久々なんで、どうやるんだっけ？って感じだったが、なんとかできた。
ついでに、素数は無限にあります。これも証明できるんだけどこっちはちょっと難しい。

素数を有限と仮定する。すなわち、 $p_1,p_2,\cdots,p_n$ を素数とし、 $p_n$ を最大の素数とする。
ここで自然数 $n=p_1p_2\cdots p_n+1$ はすべての素数で割り切れないので、この数自体が素数である。
これは、 $p_n$ が最大の素数であることに矛盾する。つまり素数は無限にある。

とまぁ、やってみれば単純なんだけどね。なかなかおもいつかないんだよねぇこれが。
素数自体はいろいろと話題のつきない数なので、調べてみると面白いかもね。
ちなみに・・・素数は暗号化に一役買っています。