今日学んだこと

読書感想文とか、勉強した内容とか

数学:素数ってなんぞ?

通勤中に、昔読んだ「世界を読み解く数学入門」という本を読み返している。

案の定内容を全く覚えていなかったので、その中に出てくる素数の話について、色々と調べつつ掘り下げてみる。なお、僕はKindle版で読んでいるが、文と解説の図を行ったり来たりするのが難しく、もし買うのであれば書籍版の方がオススメかもと思った。

 素数の定義

Wikipediaでは、素数を以下の様に定義している。

素数(そすう、prime number)とは、1 と自分自身以外に正の約数を持たない自然数で、1 でない数のことである。

自然数は何かというのをおさらいすると

自然数を 123, … とする流儀と、0123, … とする流儀があり、前者は数論などでよく使われ、後者は集合論論理学などでよく使われる(詳しくは自然数の歴史と零の地位の節を参照)。いずれにしても、0 を自然数に含めるかどうかが問題になるときは、その旨を明記する必要がある。自然数の代わりに非負整数または正整数と言い換えることによりこの問題を避けることもある。なお、日本における初等中等教育では「自然数は 1 から始まる」と指導される。 

 自然数に0が含まれるか否かは流儀によって異なるというのは知らなかった。ただ、素数を考えるにあたっては、"約数を含まない"となっているので0の事を考慮する必要はない。

1を含めない理由は、ある数を素因数分解した際に、(当たり前だけど並び順を考慮せず)一意の形式にできないからとのこと。

つまり、

28 = 22 x 7

と、一意の素因数分解が可能な所に、1を素数としてしまうと

28 = 22 x 7 x 1

とか

28 = 22 x 7 x 12

とか無限のパターンを作れてしまうので、都合が悪くなってしまうためである。

つまり、目的ベースで考えると、素数の定義を「素因数分解の要素とできる数」と言い換えることも可能である

素数の特徴

大きな特徴として、素数を簡単に見つける方法はない。これまたwikipediaでは

2013年12月現在で知られている最大の素数は、2013年1月に発見された、現在分かっている中で48番目のメルセンヌ素数 257885161 − 1 であり、十進法で表記したときの桁数は1742万5170桁に及ぶ

と記載されている。つまり、現在人類が把握している素数は、48個しかない・・・わけはなくて、メルセンヌ素数と呼ばれる特殊な素数の48番目という意味。ちなみに、素数は無限に存在することが証明されている。

素数の判断方法

これまたwikipediaからだが、

最も素朴な方法は、2 から √n 以下の素数まで順番に割っていく、試し割りと呼ばれる方法である。n が √n 以下の全ての素数で割り切れなければ n は素数である。

といったものがある。たとえば67が素数であるか判断したい場合は

  • √67 は8.18・・・
  • 8以下の素数は2,3,5,7
  • これらどれでも割り切れないので、67は素数である

という判断方法になる。

つまり、n以下の素数が全てわかっていないと、(この判断方法においては)その数字が素数か判断できないことになる。

これを、2から数え上げていくプログラムを考えてみる。

素数を数え上げるプログラム(試し割り法)

実行結果は以下の通り

$ python ./primenumber.py
2 is prime number. #1
3 is prime number. #2
5 is prime number. #3
7 is prime number. #4
11 is prime number. #5
13 is prime number. #6
17 is prime number. #7
19 is prime number. #8
23 is prime number. #9
29 is prime number. #10
〜中略〜
463 is prime number. #90
467 is prime number. #91
479 is prime number. #92
487 is prime number. #93
491 is prime number. #94
499 is prime number. #95
503 is prime number. #96
509 is prime number. #97
521 is prime number. #98
523 is prime number. #99
541 is prime number. #100

 うちのオンボロMac Miniでも、10万個目くらいまでなら一瞬で出てくる。ただ、4桁万の素数を割り出すとなると、僕が死ぬ方が先になってしまう。