素数表　　　　　　　　　　　　　　　　　　　　　　　　　　

　素数とは、１以外の数で１と自分自身しか約数がない整数のことをいう。

例えば、２、３、５、７、・・・などが素数である。

素数が無限個あることは、紀元前３００年頃、ユークリッドにより、示されている。

　もし、素数が有限個とすると、最大の素数Ｎが存在する。このとき、２からＮまでの全ての
素数の積に １ を加えた数Ｍを作ると、ＭはＮより大きい整数で、ＭはＮ以下の全ての素数
では割り切れない。ということは、Ｍは素数かまたはＮより大きい素数で割り切れる。いず
れにしても、これは、Ｎが最大の素数であることに矛盾する。よって、素数は無限個ある。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（ユークリッド原論）

　素数が無限個あることが分かったので、素数全てを求めるという野望は放棄せざるをえ
ない。そのかわり、ある数が素数かどうかを能率的に判定する方法や素数がどんなふうに
出現するのかなど、興味の種は尽きない。

　与えられた整数 ｎ が素数かどうかは、２、３、５、７、．．．と　ｎ より小さい素数でどんどん
割っていき、割り切れなければ、素数である。

　どこまで割っていくのかというと、ｎ の平方根以下で十分である。

素数の抽出には、エラトステネスのふるい法が有名である。

　整数 ｎ より大きくない素数の個数を π（ｎ） とする。

ｎ が十分大きいとき、π（ｎ） の値は、ｎ÷ｌｎ（ｎ） の値にほぼ等しい
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（但し、ｌｎ（ｎ） は自然対数）

ということを、数学者ガウスは、１７９２年１５歳のとき発見した。

　この予想は、１８９６年アダマールとド・ラ・ヴァレー・プサンにより、独立に証明された。

素数定理といわれるこの定理は、数学の中で最も美しい定理の１つといわれている。

　この定理により、与えられた任意の整数 ｎ をこえない素数の個数が大体予知できるよう
になった。

　次に、１０００以下の素数表をあげる。

　１０００以下の素数は、全部で１６８個ある。素数定理に当てはめてみれば、１４４．８なの
で、ほぼ近い。ガウスの偉大さが実感できる。

　因みに、２０００以下は、３０３個（２６３．１）、３０００以下は、４３０個（３７４．７）、５０００以
下は、６６９個（４８２．３）、１００００個以下は１２２９個（１０８５．７）の素数がある。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（　）内は、素数定理による数値。

（参考文献：Ｍ．ラインズ著　片山孝次　訳　「数　その意外な表情」（岩波書店）
　　　　　　　　和田秀男著　「数の世界　整数論への道」（岩波書店）
　　　　　　　　問谷　力・森本清吾著　「袖珍　数学公式要覧」（山海堂出版部））

（追記）　平成１５年５月１８日、矢倉さんという方から、素数の個数について、誤りのご指
　　　　　摘をいただいた。検証の結果、ご指摘の通りであるので、本文を訂正した。
　　　　　　矢倉さんに感謝いたします。

　　　　　２〜９９９９ までの素数表について（→　参考HP）

　　　　　また、次のHPでは、素数表を指定した範囲内で作成することができる。（矢倉さん）
　　　　　　　ｈｔｔｐ：//ｗｗｗ．ａｉｅｓｔａｔｅ．ｃｏｍ/ｐｒｉｍｅ．ｐｈｐ
　　　　　（上記HPは、矢倉さんが全く実験的に作っただけのページで、遠からず削除するこ
　　　　　　とになるとのことである。そのような事情から、当HPからのリンクを解除させてい
　　　　　　ただきました。― 2003.5.20）

　　　　　上記ＨＰで、試しに、１００万以下の素数の個数を計算してみた。
　　　　　結果は、７８４９８個で、約５５４．２６秒（９分強）要した。思わず感動してしまった！


（追記）　平成２０年３月２０日付け

　当ＨＰの掲示板「出会いの泉」に、ｚｋ４３さんが、ある数までの素数を求めるための、Ｅｘｃｅｌ
の ＶＢＡ を利用したプログラムを紹介された。上記で、９分強かかったという一文を読まれて
の書き込みである。ｚｋ４３さんに感謝いたします。

　ｎ の平方根以下の数で割り算するというアイデアを利用したＶＢＡである。

　　　　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

　Ｖｉｓｕａｌ　Ｂａｓｉｃ　Ｅｄｉｔｏｒ　を起動させて、標準モジュールに上記を記述し、マクロを実行さ
せればよい。

　私のパソコン（Pentium(R) ４　CPU 2.93GＨz)で、早速、Excelに上記のVBAを覚え込ませ
て実行してみたところ、２１秒！で７８４９８個と出ました。速かったでね。
（この結果は、らすかるさんのＨＰにある表の数字と一致している。）

　また、当ＨＰがいつもお世話になっている、らすかるさんは、今年の１月に、素数の個数を
求めるプログラムの高速化に挑戦されたとのことである。

　プログラム言語が、C とアセンプで、アルゴリズムも違うのでＶＢＡのプログラムとは比較で
きないが、実行時間は下記のようであったとのことである。（CPUは Core2 2.4GHz）

　　1000万まで：　0.04秒　・・・・　０．０４秒くらい！（映画のフィルム１コマ分の時間）
　　1億まで：　0.16秒　・・・・　０．２秒くらい！（人間の反応速度）
　　10億まで：　1.51秒　・・・・　２秒くらい！（光が地球から月まで進む時間）
　　100億まで：　16.3秒　・・・・　１５秒くらい！（小学５年女子１００ｍ記録）
　　1000億まで：　180秒　・・・・　３分くらい！（小学５年男子１０００ｍ記録）
　　1兆まで：　34分　・・・・　３０分くらい！（大学生１００００ｍ記録）
　　10兆まで：　428分　・・・・　７時間くらい！（ウルトラマラソン１００ｋｍ記録）
　　100兆まで：　108時間3分 ・・・・　４日半くらい！

（コメント）　私のパソコンで、２１秒かかった計算も、らすかるさんのアルゴリズムにかかる
　　　　　　と、ほんの一瞬で求まってしまうような．．．予感。いや〜、高速すぎますね！


（追記）　２００３年１２月３日、過去最大の素数が発見された（検証により、確認）。

　　　　　　　６３２万４３０桁の数で、４０番目のメルセンヌ数だという。

　　　　　　ミシガン州立大学の大学院生マイケル・シェイファー（Ｍｉｃｈａｅｌ　Ｓｈａｆｅｒ）さんが
　　　　　中心となって、世界中の２００万台を越えるパソコンを結んで、２年がかりの計算で
　　　　　発見されたとのことである。

（追記）　２００４年５月１５日、過去最大の素数が発見された（検証により、確認）。

　　　　　　　　　　　　　　　　　　　　　　　　　　　２^24036583−１

　　　　　　　７２３万５７３３桁の数で、４１番目のメルセンヌ数だという。


（追記）　２００５年２月２７日、過去最大の素数が発見された（検証により、確認）。

　　　　　　　　　　　　　　　　　　　　　　　　　　　２^25964951−１

　　　　　　　７８１万６２３０桁の数で、４２番目のメルセンヌ数だという。


（追記）　２００５年１２月１５日、過去最大の素数が発見された（検証により、確認）。

　　　　　　　　　　　　　　　　　　　　　　　　　　　２^30402457−１

　　　　　　　９１５万２０５２桁の数で、４３番目のメルセンヌ数なのかな？


（追記）　２００６年９月４日、過去最大の素数が発見された（検証により、確認）。

　　　　　　　　　　　　　　　　　　　　　　　　　　　２^32582657−１

　　　　　　　９８０万８３５８桁の数で、４４番目のメルセンヌ数なのかな？


（追記）　２００８年８月２３日、過去最大の素数が発見された（検証により、確認）。

　　　　　　　　　　　　　　　　　　　　　　　　　　　２^43112609−１

　　　　　　　１２９７万８１８９桁の数で、４７番目のメルセンヌ数なのかな？

　　　　発見者は、Edson　Smith


（追記）　２００８年９月６日、過去最大の素数が発見された（検証により、確認）。

　　　　　　　　　　　　　　　　　　　　　　　　　　　２^37156667−１

　　　　　　　１１１８万５２７２桁の数で、４５番目のメルセンヌ数なのかな？


（追記）　２００９年４月１２日、過去最大の素数が発見された（検証により、確認）。

　　　　　　　　　　　　　　　　　　　　　　　　　　　２^42643801−１

　　　　　　　１２８３万７０６４桁の数で、４６番目のメルセンヌ数なのかな？

　　　　発見者は、Odd　Ｍ．Strindmo


（追記）　２０１３年１月２５日、過去最大の素数が発見された（検証により、確認）。

　　　　　　　　　　　　　　　　　　　　　　　　　　　２^57885161−１

　　　　　　　１７４２万５１７０桁の数だという。４８番目のメルセンヌ数なのかな？

　　　米国・セントラルミズーリ大学のクーパー教授が見つけたと、世界各地のボランティアの
　　コンピュータをつないで素数探しをするプロジェクト、ＧＩＭＰＳが発表した。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（２０１３年２月７日付け朝日新聞夕刊）


（追記）　２０１６年１月２１日、過去最大の素数が発見された（検証により、確認）。

　　　　　　　　　　　　　　　　　　　　　　　　　　　２^74207281−１
　　　　　　　　　　　　　　　　　　　（３００３７６４１８０・・・・・・・１０８６４３６３５１）

　　　　　　　２２３３万８６１８桁の数だという。４９番目のメルセンヌ数なのかな？

　Ａ４判の紙にびっしり印刷しても約１万枚必要とのことで、その膨大な量に圧倒される。

　米国・セントラルミズーリ大学は、過去最大の素数をクーパー教授が見つけたと、１月２１
日、発表した。クーパー教授は、世界各地のボランティアのコンピュータをつないで素数探し
をするプロジェクト「ＧＩＭＰＳ」のメンバー。

　２０１５年９月１７日にコンピュータは新たな素数を見つけていたが、発見に気付いたのは、
２０１６年１月７日であったという。（２０１６年１月２４日付け朝日新聞夕刊）


　　（現在知られている最大の素数については、「完全数」を参照）


（追記）　２０１７年１２月２６日、過去最大の素数が発見されたようだ。

　　　　　　　　　　　　　　　　　　　　　　　　　　　２^77232917−１

　　　　　　十進法では、２３２４万９４２５ 桁の数だという。

　　　　発見者は、Jon　Pace


（追記）　２０１８年１２月、過去最大の素数が発見されたようだ。

　　　　　　　　　　　　　　　　　　　　　　　　　　　２^82589933−１

　　　　　　十進法では、２４８６万２０４８ 桁の数だという。


　メルセンヌ素数についての最新情報


（追記）　当ＨＰの掲示板「出会いの泉」に、当ＨＰ読者ＮＨＮ「ラフィエル」さんが素数を求め
　　　　　る式について投稿された。（平成２５年３月２２日付け）

　素数を求める式で、フェルマー数以外で、これと同じか似たような数式はありますか？

　３ⁿ＋２^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


　空舟さんからのコメントです。（平成２５年３月２３日付け）

　３ⁿを５で割った余りは、３、４、２、１ と循環し、２^mを５で割った余りは、２、４、３、１ と循環
するので、ｎ＝ｍ＝５に限らず、ｎ＝ｍ＝２N＋１ の場合は、常に5で割り切れます。

　３ⁿ＋２^m≡０　(ｍｏｄ　７) を解くことを考える。２^m≡９^m　(ｍｏｄ　７) から、

　３ⁿ＋９^m≡０　、３ⁿ/９^m≡−１　、３^n-2m≡−１　(ｍｏｄ　７)　となるので、

３³≡−１　(ｍｏｄ　７) に注意して、ｎ−２ｍ≡３　(ｍｏｄ　６) の場合は、７で割り切れるはず
です。

　従って、必ず素数になるというわけではないですが、GAIさんの調査のように素数がよく出
てくるようです。

　よく「素数を与える数式」としては、オイラーが見つけたとされる「ｘ²＋ｘ＋４１」という式が有
名だと思います。

　ｘ＝４１　だともちろん素数にならないですが、ｘ＝１からｘ＝３９までは全部素数になります。

　この話題については、Ｗｅｂサイト「■素数を表す公式・表さない公式」が参考になると思い
ます。


（追記）　令和２年９月２７日付け

　「７３９３９１３３」は素数で、右側から順に数字を取り去った数

　７３９３９１３　、７３９３９１　、７３９３９　、７３９３　、７３９　、７３　、７

も素数であり続ける。素数の中の素数と言われる所以である。この性質を持つ素数として、

　　５３、３１７、５９９、７９７、２３９３、・・・、７３９３９１３３

が知られている。