素数とは、1以外の数で1と自分自身しか約数がない整数のことをいう。
例えば、2、3、5、7、・・・などが素数である。
素数が無限個あることは、紀元前300年頃、ユークリッドにより、示されている。
もし、素数が有限個とすると、最大の素数Nが存在する。このとき、2からNまでの全ての
素数の積に 1 を加えた数Mを作ると、MはNより大きい整数で、MはN以下の全ての素数
では割り切れない。ということは、Mは素数かまたはNより大きい素数で割り切れる。いず
れにしても、これは、Nが最大の素数であることに矛盾する。よって、素数は無限個ある。
(ユークリッド原論)
素数が無限個あることが分かったので、素数全てを求めるという野望は放棄せざるをえ
ない。そのかわり、ある数が素数かどうかを能率的に判定する方法や素数がどんなふうに
出現するのかなど、興味の種は尽きない。
与えられた整数 n が素数かどうかは、2、3、5、7、...と n より小さい素数でどんどん
割っていき、割り切れなければ、素数である。
どこまで割っていくのかというと、n の平方根以下で十分である。
素数の抽出には、エラトステネスのふるい法が有名である。
整数 n より大きくない素数の個数を π(n) とする。
n が十分大きいとき、π(n) の値は、n÷ln(n) の値にほぼ等しい
(但し、ln(n)
は自然対数)
ということを、数学者ガウスは、1792年15歳のとき発見した。
この予想は、1896年アダマールとド・ラ・ヴァレー・プサンにより、独立に証明された。
素数定理といわれるこの定理は、数学の中で最も美しい定理の1つといわれている。
この定理により、与えられた任意の整数 n をこえない素数の個数が大体予知できるよう
になった。
次に、1000以下の素数表をあげる。
2 | 79 | 191 | 311 | 439 | 577 | 709 | 857 |
3 | 83 | 193 | 313 | 443 | 587 | 719 | 859 |
5 | 89 | 197 | 317 | 449 | 593 | 727 | 863 |
7 | 97 | 199 | 331 | 457 | 599 | 733 | 877 |
11 | 101 | 211 | 337 | 461 | 601 | 739 | 881 |
13 | 103 | 223 | 347 | 463 | 607 | 743 | 883 |
17 | 107 | 227 | 349 | 467 | 613 | 751 | 887 |
19 | 109 | 229 | 353 | 479 | 617 | 757 | 907 |
23 | 113 | 233 | 359 | 487 | 619 | 761 | 911 |
29 | 127 | 239 | 367 | 491 | 631 | 769 | 919 |
31 | 131 | 241 | 373 | 499 | 641 | 773 | 929 |
37 | 137 | 251 | 379 | 503 | 643 | 787 | 937 |
41 | 139 | 257 | 383 | 509 | 647 | 797 | 941 |
43 | 149 | 263 | 389 | 521 | 653 | 809 | 947 |
47 | 151 | 269 | 397 | 523 | 659 | 811 | 953 |
53 | 157 | 271 | 401 | 541 | 661 | 821 | 967 |
59 | 163 | 277 | 409 | 547 | 673 | 823 | 971 |
61 | 167 | 281 | 419 | 557 | 677 | 827 | 977 |
67 | 173 | 283 | 421 | 563 | 683 | 829 | 983 |
71 | 179 | 293 | 431 | 569 | 691 | 839 | 991 |
73 | 181 | 307 | 433 | 571 | 701 | 853 | 997 |
1000以下の素数は、全部で168個ある。素数定理に当てはめてみれば、144.8なの
で、ほぼ近い。ガウスの偉大さが実感できる。
因みに、2000以下は、303個(263.1)、3000以下は、430個(374.7)、5000以
下は、669個(482.3)、10000個以下は1229個(1085.7)の素数がある。
( )内は、素数定理による数値。
(参考文献:M.ラインズ著 片山孝次 訳 「数 その意外な表情」(岩波書店)
和田秀男著 「数の世界 整数論への道」(岩波書店)
問谷 力・森本清吾著 「袖珍 数学公式要覧」(山海堂出版部))
(追記) 平成15年5月18日、矢倉さんという方から、素数の個数について、誤りのご指
摘をいただいた。検証の結果、ご指摘の通りであるので、本文を訂正した。
矢倉さんに感謝いたします。
2〜9999 までの素数表について(→ 参考HP)
また、次のHPでは、素数表を指定した範囲内で作成することができる。(矢倉さん)
http://www.aiestate.com/prime.php
(上記HPは、矢倉さんが全く実験的に作っただけのページで、遠からず削除するこ
とになるとのことである。そのような事情から、当HPからのリンクを解除させてい
ただきました。― 2003.5.20)
上記HPで、試しに、100万以下の素数の個数を計算してみた。
結果は、78498個で、約554.26秒(9分強)要した。思わず感動してしまった!
(追記) 平成20年3月20日付け
当HPの掲示板「出会いの泉」に、zk43さんが、ある数までの素数を求めるための、Excel
の VBA を利用したプログラムを紹介された。上記で、9分強かかったという一文を読まれて
の書き込みである。zk43さんに感謝いたします。
n の平方根以下の数で割り算するというアイデアを利用したVBAである。
Sub 素数の個数()
p = 0
For Num = 2 To 1000000
a = Int(Num ^ 0.5)
c = 0
For k = 2 To a
If Num Mod k = 0 Then
c = 1
Exit For
End If
Next k
If c = 0 Then p = p + 1
Next Num
Range("A1") = p
End Sub
Visual Basic Editor を起動させて、標準モジュールに上記を記述し、マクロを実行さ
せればよい。
私のパソコン(Pentium(R) 4 CPU 2.93GHz)で、早速、Excelに上記のVBAを覚え込ませ
て実行してみたところ、21秒!で78498個と出ました。速かったでね。
(この結果は、らすかるさんのHPにある表の数字と一致している。)
また、当HPがいつもお世話になっている、らすかるさんは、今年の1月に、素数の個数を
求めるプログラムの高速化に挑戦されたとのことである。
プログラム言語が、C とアセンプで、アルゴリズムも違うのでVBAのプログラムとは比較で
きないが、実行時間は下記のようであったとのことである。(CPUは Core2 2.4GHz)
1000万まで: 0.04秒 ・・・・ 0.04秒くらい!(映画のフィルム1コマ分の時間)
1億まで: 0.16秒 ・・・・ 0.2秒くらい!(人間の反応速度)
10億まで: 1.51秒 ・・・・ 2秒くらい!(光が地球から月まで進む時間)
100億まで: 16.3秒 ・・・・ 15秒くらい!(小学5年女子100m記録)
1000億まで: 180秒 ・・・・ 3分くらい!(小学5年男子1000m記録)
1兆まで: 34分 ・・・・ 30分くらい!(大学生10000m記録)
10兆まで: 428分 ・・・・ 7時間くらい!(ウルトラマラソン100km記録)
100兆まで: 108時間3分 ・・・・ 4日半くらい!
(コメント) 私のパソコンで、21秒かかった計算も、らすかるさんのアルゴリズムにかかる
と、ほんの一瞬で求まってしまうような...予感。いや〜、高速すぎますね!
(追記) 2003年12月3日、過去最大の素数が発見された(検証により、確認)。
632万430桁の数で、40番目のメルセンヌ数だという。
ミシガン州立大学の大学院生マイケル・シェイファー(Michael Shafer)さんが
中心となって、世界中の200万台を越えるパソコンを結んで、2年がかりの計算で
発見されたとのことである。
(追記) 2004年5月15日、過去最大の素数が発見された(検証により、確認)。
224036583−1
723万5733桁の数で、41番目のメルセンヌ数だという。
(追記) 2005年2月27日、過去最大の素数が発見された(検証により、確認)。
225964951−1
781万6230桁の数で、42番目のメルセンヌ数だという。
(追記) 2005年12月15日、過去最大の素数が発見された(検証により、確認)。
230402457−1
915万2052桁の数で、43番目のメルセンヌ数なのかな?
(追記) 2006年9月4日、過去最大の素数が発見された(検証により、確認)。
232582657−1
980万8358桁の数で、44番目のメルセンヌ数なのかな?
(追記) 2008年8月23日、過去最大の素数が発見された(検証により、確認)。
243112609−1
1297万8189桁の数で、47番目のメルセンヌ数なのかな?
発見者は、Edson Smith
(追記) 2008年9月6日、過去最大の素数が発見された(検証により、確認)。
237156667−1
1118万5272桁の数で、45番目のメルセンヌ数なのかな?
(追記) 2009年4月12日、過去最大の素数が発見された(検証により、確認)。
242643801−1
1283万7064桁の数で、46番目のメルセンヌ数なのかな?
発見者は、Odd M.Strindmo
(追記) 2013年1月25日、過去最大の素数が発見された(検証により、確認)。
257885161−1
1742万5170桁の数だという。48番目のメルセンヌ数なのかな?
米国・セントラルミズーリ大学のクーパー教授が見つけたと、世界各地のボランティアの
コンピュータをつないで素数探しをするプロジェクト、GIMPSが発表した。
(2013年2月7日付け朝日新聞夕刊)
(追記) 2016年1月21日、過去最大の素数が発見された(検証により、確認)。
274207281−1
(3003764180・・・・・・・1086436351)
2233万8618桁の数だという。49番目のメルセンヌ数なのかな?
A4判の紙にびっしり印刷しても約1万枚必要とのことで、その膨大な量に圧倒される。
米国・セントラルミズーリ大学は、過去最大の素数をクーパー教授が見つけたと、1月21
日、発表した。クーパー教授は、世界各地のボランティアのコンピュータをつないで素数探し
をするプロジェクト「GIMPS」のメンバー。
2015年9月17日にコンピュータは新たな素数を見つけていたが、発見に気付いたのは、
2016年1月7日であったという。(2016年1月24日付け朝日新聞夕刊)
(現在知られている最大の素数については、「完全数」を参照)
(追記) 2017年12月26日、過去最大の素数が発見されたようだ。
277232917−1
十進法では、2324万9425 桁の数だという。
発見者は、Jon Pace
(追記) 2018年12月、過去最大の素数が発見されたようだ。
282589933−1
十進法では、2486万2048 桁の数だという。
メルセンヌ素数についての最新情報
(追記) 当HPの掲示板「出会いの泉」に、当HP読者NHN「ラフィエル」さんが素数を求め
る式について投稿された。(平成25年3月22日付け)
素数を求める式で、フェルマー数以外で、これと同じか似たような数式はありますか?
3n+2m (条件: n+m=6x にならない 1≧n−m≧−1、n>0、m>0)
が素数になる、はずです・・・。(高校の授業中に考えたものです。)
GAI さんからのコメントです。(平成25年3月22日付け)
n=m=5 の場合、275 となり素数とはなりません。それでも多くの場合が素数になるの
は面白い式ですね。mを200までで調査してみました。
m; n|素数
1; 1|5
1; 2|11
2; 1|7
2; 2|13
2; 3|31
3; 2|17
3; 4|89
4; 3|43
4; 4|97
5; 4|113
5; 6|761
6; 5|307
6; 7|2251
7; 6|857
7; 8|6689
9; 10|59561
10; 9|20707
12; 11|181243
13; 12|539633
14; 15|14365291
16; 15|14414443
18; 17|129402307
20; 21|10461401779
23; 22|31389448217
23; 24|282437925089
33; 32|1853028778786433
34; 33|5559077746424707
35; 36|150094669656737489
36; 35|50031613818476443
37; 36|150094772735952593
47; 46|8862938260389989451257
48; 47|26588814640432479998443
48; 49|239299329512092506300739
50; 51|2153693964201457673153371
60; 59|14130386092891656009371658043
64; 63|1144561273449284238959659248043
81; 80|147808829414348341167722439464732709953
85; 86|107752636643058216783050887908587014548761
102;101|1546132562196033998179985790209781424093135387507
115;116|22185312344622607536006721455233772938700782582212169489
133;134|8595044557171427132038727205005467577310247078756525985114451161
155;154|29969067287845284806900763424259354345695037325432711901413781193689500137
160;159|7282483350946404208076885502458246684853252953174602126320557669210243328043
174;173|34831892110592771988701292967840845906028956537826662489172367497298175100125242707
175;176|940461086986004843694934910131104208392131088686023657900173332902199657733778583489
空舟さんからのコメントです。(平成25年3月23日付け)
3nを5で割った余りは、3、4、2、1 と循環し、2mを5で割った余りは、2、4、3、1 と循環
するので、n=m=5に限らず、n=m=2N+1 の場合は、常に5で割り切れます。
3n+2m≡0 (mod 7) を解くことを考える。2m≡9m (mod 7) から、
3n+9m≡0 、3n/9m≡−1 、3n-2m≡−1 (mod 7) となるので、
33≡−1 (mod 7) に注意して、n−2m≡3 (mod 6) の場合は、7で割り切れるはず
です。
従って、必ず素数になるというわけではないですが、GAIさんの調査のように素数がよく出
てくるようです。
よく「素数を与える数式」としては、オイラーが見つけたとされる「x2+x+41」という式が有
名だと思います。
x=41 だともちろん素数にならないですが、x=1からx=39までは全部素数になります。
この話題については、Webサイト「■素数を表す公式・表さない公式」が参考になると思い
ます。
(追記) 令和2年9月27日付け
「73939133」は素数で、右側から順に数字を取り去った数
7393913 、739391 、73939 、7393 、739 、73 、7
も素数であり続ける。素数の中の素数と言われる所以である。この性質を持つ素数として、
53、317、599、797、2393、・・・、73939133
が知られている。