素数表　　　　　　　　　　　　　　　　　　　　　　　　　　

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　　　　２〜９９９９ までの素数表については、次の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分 ・・・・　４日半くらい！

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


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

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

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

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