素数表　　　　　　　　　　　　　　　　　　　　　　　　　　

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

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

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

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


（追記）　令和４年３月１日付け

　素数は無限個存在するが、いったいどこに存在するのだろうか？このことを示す重要な定
理として、ベルトラン＝チェビシェフの定理が知られている。ベルトランが予想し、チェビシェ
フが証明したものである。

ベルトラン＝チェビシェフの定理　　ｘ≧２に対して、ｘと２ｘの間に必ず素数が存在する。

例　２と４の間には、素数３が存在する。

例　４と８の間には、素数５や７が存在する。


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

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

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

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


　「エラトステネスの篩」について、ＧＡＩさんからのご投稿です。（令和３年３月１日付け）

　エラトステネスの篩でチェックされていく順に並べた表を作ってみました。

　第一行が2を先頭にその倍数が限りなく右に並んでいきます。（都合のため15個並んだ
地点で止めたものと解釈してください。）

　次の第二行はチェックを受けていない最小の数(3)からその倍数をチェックしていきます。
但し6は既にチェック済みなので、この行には入りません。

　以下同様にして、チェックされていく順番に下にさがっていきます。

[ 2    4    6    8   10   12   14   16   18   20   22   24   26   28   30 ..]
[ 3    9   15   21   27   33   39   45   51   57   63   69   75   81   87 ..]
[ 5   25   35   55   65   85   95  115  125  145  155  175  185  205  215 ..]
[ 7   49   77   91  119  133  161  203  217  259  287  301  329  343  371 ..]
[11  121  143  187  209  253  319  341  407  451  473  517  583  649  671 ..]
[13  169  221  247  299  377  403  481  533  559  611  689  767  793  871 ..]
[17  289  323  391  493  527  629  697  731  799  901 1003 1037 1139 1207 ..]
[19  361  437  551  589  703  779  817  893 1007 1121 1159 1273 1349 1387 ..]
[23  529  667  713  851  943  989 1081 1219 1357 1403 1541 1633 1679 1817 ..]
[29  841  899 1073 1189 1247 1363 1537 1711 1769 1943 2059 2117 2291 2407 ..]
[31  961 1147 1271 1333 1457 1643 1829 1891 2077 2201 2263 2449 2573 2759 ..]
[37 1369 1517 1591 1739 1961 2183 2257 2479 2627 2701 2923 3071 3293 3589 ..]
[41 1681 1763 1927 2173 2419 2501 2747 2911 2993 3239 3403 3649 3977 4141 ..]
[43 1849 2021 2279 2537 2623 2881 3053 3139 3397 3569 3827 4171 4343 4429 ..]
[47 2209 2491 2773 2867 3149 3337 3431 3713 3901 4183 4559 4747 4841 5029 ..]
[･･･････････････････････････････････････････････････････････････････････････]

　一応15行まで下がった地点までの15×15行列として表を眺めてみると、右下対角線に並
んでくる数列

　2，9，35，91，209，377，629，817，･･･

には面白いことに、

　　[n番目の素数]*[(2*n-2)番目の素数]　(n=2,3,4,･･･)

という関係の数が勢揃いすることになる。

2=2　、3*3=9　、5*7=35　、7*13=91　、11*19=209　、13*29=377　、17*37=629　、19*43=817
23*53=1219　、29*61=1769　、31*71=2201　、37*79=2923　、41*89=3649　、43*101=4343
47*107=5029　、53*113=5989　、59*131=7729　、61*139=8479　、67*151=10117
71*163=11573　、73*173=12629　、79*181=14299　、83*193=16019　、89*199=17711
97*223=21631　、101*229=23129　、･･････


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

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

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

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

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

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

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

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

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

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

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

　　　　　　１００００ までの素数表について（→　参考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さんの調査のように素数がよく出
てくるようです。

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

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

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


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

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

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

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

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

が知られている。


（追記）　令和３年２月２８日付け

　素数表で、１０００以下の素数は全部で１６８個あることが知られているが、この個数に関
する問題が、一橋大学前期（２０２１）で出題された。

一橋大学　前期（２０２１）

第１問　１０００以下の素数は、２５０個以下であることを示せ。


　１０００以下なので、エラトステネスのふるいでも求められるかな？

　以下は、スマートに包除原理を用いて、２または３または５または７で割り切れる数の個数
を求めてみよう。

（解）　１０００以下の自然数で、２の倍数、３の倍数、５の倍数、７の倍数の集合をそれぞれ

　Ａ、Ｂ、Ｃ、Ｄとおく。このとき、２または３または５または７で割り切れる数の集合をＸとおく。

ｎ（Ａ）で、集合Ａの要素の個数を表すものとする。集合の包除原理から、

ｎ（Ｘ）＝ｎ（Ａ）＋ｎ（Ｂ）＋ｎ（Ｃ）＋ｎ（Ｄ）

　　　　−ｎ（Ａ∩Ｂ）−ｎ（Ａ∩Ｃ）−ｎ（Ａ∩Ｄ）−ｎ（Ｂ∩Ｃ）−ｎ（Ｂ∩Ｄ）−ｎ（Ｃ∩Ｄ）

　　　　＋ｎ（Ａ∩Ｂ∩Ｃ）＋ｎ（Ａ∩Ｂ∩Ｄ）＋ｎ（Ａ∩Ｃ∩Ｄ）＋ｎ（Ｂ∩Ｃ∩Ｄ）

　　　　−ｎ（Ａ∩Ｂ∩Ｃ∩Ｄ）

　ここで、

ｎ（Ａ）＝［１０００/２］＝５００　、ｎ（Ｂ）＝［１０００/３］＝３３３　、ｎ（Ｃ）＝［１０００/５］＝２００

ｎ（Ｄ）＝［１０００/７］＝１４２

ｎ（Ａ∩Ｂ）＝［１０００/６］＝１６６　、ｎ（Ａ∩Ｃ）＝［１０００/１０］＝１００

ｎ（Ａ∩Ｄ）＝［１０００/１４］＝７１　、ｎ（Ｂ∩Ｃ）＝［１０００/１５］＝６６

ｎ（Ｂ∩Ｄ）＝［１０００/２１］＝４７　、ｎ（Ｃ∩Ｄ）＝［１０００/３５］＝２８

ｎ（Ａ∩Ｂ∩Ｃ）＝［１０００/３０］＝３３　、ｎ（Ａ∩Ｂ∩Ｄ）＝［１０００/４２］＝２３

ｎ（Ａ∩Ｃ∩Ｄ）＝［１０００/７０］＝１４　、ｎ（Ｂ∩Ｃ∩Ｄ）＝［１０００/１０５］＝９

ｎ（Ａ∩Ｂ∩Ｃ∩Ｄ）＝［１０００/２１０］＝４

なので、

ｎ（Ｘ）＝５００＋３３３＋２００＋１４２−１６６−１００−７１−６６−４７−２８
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　＋３３＋２３＋１４＋９−４＝７７２

　７７２個のうち、２、３、５、７の４個は素数なので、１０００以下の自然数には少なくとも７６８

個の合成数があることが示された。すなわち、素数は、多くても　１０００−７６８＝２３２（個）

あり、１０００以下の素数は２５０個以下であることが示された。　　（終）


（追記）　令和４年３月２４日付け

　次の素数に関わる問題が、２０２２年度の女子学院中学入試で出題された。問題は若干
改題しました。

問題　　Ａ、Ｂを整数とし、Ａ以上Ｂ未満の素数の個数をＡ☆Ｂで表す。次の問いに答えよ。

（１）　１０☆５０を求めよ。

（２）　（２０☆Ａ）×（Ａ☆Ｂ）×（Ｂ☆５０）＝９　となるＡ、Ｂの組のうち、Ａ＋Ｂが最も大きくな
　　るようなＡ、Ｂの値を求めよ。


　解答に入る前に、１０以上で５０未満の素数は、冒頭の素数表で、

　　１１　、１３　、１７　、１９　、２３　、２９　、３１　、３７　、４１　、４３　、４７

の１１個あることが分かる。よって、（１）は容易だろう。

（解）（１）　１０☆５０＝１１

（２）　（２０☆Ａ）×（Ａ☆Ｂ）×（Ｂ☆５０）＝９　において、２０☆Ａ、Ａ☆Ｂ、Ｂ☆５０が１以上の
　　　整数であることを考えると、起こり得る場合は、Ａ、Ｂが最大を考えて

　　２０☆Ａ＝９、Ａ☆Ｂ＝１、Ｂ☆５０＝１　→　起こりえない

　　２０☆Ａ＝１、Ａ☆Ｂ＝９、Ｂ☆５０＝１　→　起こりえない

　　２０☆Ａ＝１、Ａ☆Ｂ＝１、Ｂ☆５０＝９　→　起こりえない

　　２０☆Ａ＝３、Ａ☆Ｂ＝３、Ｂ☆５０＝１　→　Ａ＝３７　、Ｂ＝４７

　　２０☆Ａ＝３、Ａ☆Ｂ＝１、Ｂ☆５０＝３　→　Ａ＝３７　、Ｂ＝４１

　　２０☆Ａ＝１、Ａ☆Ｂ＝３、Ｂ☆５０＝３　→　Ａ＝２９　、Ｂ＝４１

　以上から、Ａ＋Ｂが最も大きくなるようなＡ、Ｂの値は、　Ａ＝３７　、Ｂ＝４７　　（終）



　　以下、工事中！