素数表                     戻る     

 素数とは、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に一覧がある。
       http://www.kde.gr.jp/~ichi/qt/primes.html

     また、次の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年がかりの計算で
     発見されたとのことである。

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


(追記) 当HPの掲示板「出会いの泉」に、当HP読者NHN「ラフィエル」さんが素数を求め
     る式について投稿された。(平成25年3月22日付け)

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

 n+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) となるので、

3≡−1 (mod 7) に注意して、n−2m≡3 (mod 6) の場合は、7で割り切れるはず
です。

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

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

 x=41 だともちろん素数にならないですが、x=1からx=39までは全部素数になります。

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