素数表と素数メモ


このサイトについて

ここでは、素数とその性質をわかりやすく説明します。証明等は避け、結果だけを記述します。


10,000,000 未満の素数表

素数表1(        2 -    99,991 ;  56KB)
素数表2(  100,003 -   199,999 ;  59KB)
素数表3(  200,003 -   299,993 ;  56KB)
素数表4(  300,007 -   399,989 ;  55KB)
素数表5(  400,009 -   499,979 ;  54KB)
素数表6(  500,009 -   599,999 ;  53KB)
素数表7(  600,011 -   699,967 ;  52KB)
素数表8(  700,001 -   799,999 ;  52KB)
素数表9(  800,011 -   899,981 ;  51KB)
素数表10(  900,001 -   999,983 ;  50KB)
素数表11(1,000,003 - 1,999,993 ; 563KB)
素数表12(2,000,003 - 2,999,999 ; 543KB)
素数表13(3,000,017 - 3,999,971 ; 530KB)
素数表14(4,000,037 - 4,999,999 ; 523KB)
素数表15(5,000,011 - 5,999,993 ; 515KB)
素数表16(6,000,011 - 6,999,997 ; 510KB)
素数表17(7,000,003 - 7,999,993 ; 505KB)
素数表18(8,000,009 - 8,999,993 ; 502KB)
素数表19(9,000,011 - 9,999,991 ; 497KB)


素数判定

素数判定

素数判定ソースコード


素数の定義

1 とその数自身以外に約数を持たない自然数。ただし、1 を除く。

英語では prime(あるいは prime number)、ドイツ語では Primzahl、フランス語では Nombre premier、中国語では 素数、韓国語・朝鮮語では ソスー(申し訳ありません、ハングル表記できません)という。

1 を素数としないのは、おかしく感じるが、これは、素因数分解の一意性を保障するためである。 たとえば、6 は、 21×31 と一意に素因数分解できるが、1 を素数と認めると、 10×21×31 とも、 11×21×31 とも、 12×21×31 とも素因数分解できてしまう。 まあ、素因数分解の定義を変える方法もあるので、絶対とはいえないが。


素数の分布

素数は無限に存在する。古くから知られており、ユークリッドの幾何学原論に掲載されている。

素数の逆数の和は発散する。

双子素数(後述)は無限に存在する。

双子素数の逆数の和は発散する。

x 以下の素数の数は、x/log(x) で近似できる。なお、log()は、自然対数である(以下同様)。より高精度には、x 以下の素数の数は、∫2x 1/log(x) dx ≒ x/log(x) + x/(log(x))2 + 2x/(log(x))3 + 6x/(log(x))4 + ・・・ + (m-1)!x/(log(x))m + ・・・ で近似できる。

x 付近の素数の密度は、1/log(x) で近似できる。

x 以下の素数の和は、x3/3log(x) - x2/3 で近似できる。

x 以下の素数の逆数の和は、log(log(x)) で近似できる。

n 番目の素数は、n log(n) + n log(log(n)) で近似できる。


特別な素数

メルセンヌ素数: 素数であるメルセンヌ数(Mn = 2n - 1)を、メルセンヌ素数という。 メルセンヌ数 Mn が素数である必要条件は、n が素数であること。 メルセンヌ数は、素数かどうか効率的に判定することができるため(ルーカステスト)、大きな素数を発見しやすい。 既知の最大の素数は、毎年のように更新されているが、歴代の記録は、メルセンヌ素数のオンパレードである。

フェルマー素数: 素数であるフェルマー数(Fn = 22n + 1)を、フェルマー素数という。 フェルマー数 Fn が素数であるための必要十分条件は、3(Fn-1)/2 を Fn で割った余りが Fn-1 であること。 フェルマーは、フェルマー数が全て素数であると予測したが、 F5 = 4294967297 は素数ではなかった。

オイラー素数: n2 + n + 41 の形式の素数。0≦n≦39 の場合、素数となる。

双子素数: n と n+2 がともに素数である場合、これらを併せて、双子素数という。

三つ子素数: n、n+2、n+4 がともに素数である場合、これらを併せて、三つ子素数という。三つ子素数は、(3,5,7) しか存在しない。

四つ子素数: n、n+2、n+6、n+8 がともに素数である場合、これらを併せて、四つ子素数という。n+4 が欠けているのは当然で、「n、n+2、n+4、n+6 がともに素数である場合」と定義すると、四つ子素数が存在しないことになってしまう。四つ子素数は、必ず (30n+11, 30n+13, 30n+17, 30n+19) の形式となるが、この形式であっても四つ子素数とは限らない。


未解決の問題(証明も否定もされていない命題)

双子素数は無限に存在する。(双子素数の予想)

6 以上の全ての偶数は、2 つの奇素数(奇数の素数=2以外の素数)の和となる。(ゴールドバッハの予想)

6 以上の全ての自然数は、3 つの素数の和となる。(上記の予想と等価)

メルセンヌ素数は無限に存在する。

フェルマー素数は無限に存在する。


暗号における素数利用

公開鍵暗号の一種であり、現在ネットワーク上で一般に利用されている暗号であるRSA暗号では、キーの作成に2つの大きな素数 p, q を使用する。公開キーは、この積 pq である。

暗号を解読するためには、p, q を知る必要がある。pq から p, q を容易に計算できないことが、事実上暗号を解読できないことを保障する。

キーを生成するためには、素数判定(素数かどうかの判定)が必要となる。一般に、厳密な素数判定には時間がかかるため、近似的な素数判定が使用される。


2007年2月現在知られている最大の素数

232582657-1 (10進数で約1千万桁)


最初の100個の素数

  2   3   5   7  11  13  17  19  23  29
 31  37  41  43  47  53  59  61  67  71
 73  79  83  89  97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541


最初の50個の双子素数

(    3,   5) (   5,    7) (  11,   13) (  17,   19) (  29,   31)
(  41,   43) (  59,   61) (  71,   73) ( 101,  103) ( 107,  109)
( 137,  139) ( 149,  151) ( 179,  181) ( 191,  193) ( 197,  199)
( 227,  229) ( 239,  241) ( 269,  271) ( 281,  283) ( 311,  313)
( 347,  349) ( 419,  421) ( 431,  433) ( 461,  463) ( 521,  523)
( 569,  571) ( 599,  601) ( 617,  619) ( 641,  643) ( 659,  661)
( 809,  811) ( 821,  823) ( 827,  829) ( 857,  859) ( 881,  883)
(1019, 1021) (1031, 1033) (1049, 1051) (1061, 1063) (1091, 1093)
(1151, 1153) (1229, 1231) (1277, 1279) (1289, 1291) (1301, 1303)
(1319, 1321) (1427, 1429) (1451, 1453) (1481, 1483) (1487, 1489)


最初の10個の四つ子素数

(  11,   13,   17,   19)
( 101,  103,  107,  109)
( 191,  193,  197,  199)
( 821,  823,  827,  829)
(1481, 1483, 1487, 1489)
(1871, 1873, 1877, 1879)
(2081, 2083, 2087, 2089)
(3251, 3253, 3257, 3259)
(3461, 3463, 3467, 3469)
(5651, 5653, 5657, 5659)


数学もそうですが、何事も新たな気持ちで取り込むことが重要です。恐れず初体験を。

素数表と素数メモトップ   素数表 1 2 3 4 5 6 7 8 9 ...