Ｚ会新入社員ブログ

こんにちは．
東大マスターコースの戸神です．

国公立2次の出願も始まりましたね．
私が受験生の時は，
気が短かったのか出願期間開始と同時に書類を送りました．
その結果受験番号が(地方から送ったにも関わらず)31番でした．
ああ，素数だなと思いました．

最後の文が「ああ，素敵だな」と読めてしまった人は
今日のブログはここまでとなります．また4週間後に．

さて，なぜ31は素数だと分かるのでしょうか？
それは聞いたことがないからです．

我々は九九を知っているので，
2桁の数で"聞き覚えのない数"は素数の可能性が高いです．
51(=3x17)，91(=7x13)など，2桁の素因数を含む数には
注意しなければなりませんが．
ただ，その場合でも合成数ならどちらかは必ず1桁の素因数をもつので
3と7で割ってみて割り切れなければ素数と分ります．
(2と5は割るまでもなく判別可能ですね．)

まぁ結局は全部試してみるしかないのです．
Mという数があったら，2からM-1までで割ってみればよいです．
実際は，Mの平方根より大きい数では割る必要はないですが．
(少なくとも一方の素因数はMの平方根以下なので．)

学生時代はコンピュータプログラミングで色々な素数判定を書きましたが
素数をリストアップする際，効率が良かったのがエラトステネスのふるいでした．
範囲を決めて数字を書き出して，
2 3 4 5 6 7 8 9 10 11 12 13 14 15
左端の倍数を消していきます．左端は素数確定です．
<2> 3 5 7 9 11 13 15
左端を素数確定にして，同じことをします．
<2> <3> 5 7 11 13
以下繰り返すと素数のみが残ります．
<2> <3> <5> <7> <11> <13>
いくつもの素数を判定するる問題などでは便利でした．

エラトステネスのふるい，って学校で少しだけ習ったけど
試験の問題を解くのには全く役に立たない代物です．
大学入試でも出ません．
でも，大学生になってこの手法の有用さが分かりました．
ユークリッドの互助法もそうでした．

10年後に役に立つ内容だった！というと大げさですが，
馬鹿にしていたものに知恵を感じると，少し賢くなったかなと思ったり．

• Posted at 19:27
• 2007新入社員
• この記事のURL
• コメント(2)
• トラックバック(0)