素数を求める方法

1000以下の素数をしめします｡

2!!=2 3!!=6 5!!=30 7!!=210 11!!=2310 です。

ここで,n!!±1を考えてみましょう。
2!!±1=1,3　素数
3!!±1=5,7　素数
5!!±1=29,31素数ですが5を超え,30以下の素数は7,11,13,17,19,23もあります｡
7!!±1=209,211　ですが209=11×19です｡7を超え210以下の素数は一杯あります｡

さて、6n±1は2,3の倍数を除いた整数表現ですが、以下では素数候補と呼びます｡
n=1 5,7
n=2 11,13
n=3　17,19
n=4　23,25
n=5　29,31
n=6　35,37
n=7　41,43
n=8　47,49
となりますが,
5!!の場合,5を超え5の二乗の25未満の素数候補は、7,11,13,17,19,23は25以下なので,5ですらわれないので全て素数です｡では25を超え5!!未満の数は29でこれも素数です｡5!!+1の31も素数です｡
これで,5!!+1までの素数は全てもとまりました｡

では7!!の場合,7の二乗であり49未満の未出の素数候補は、35,37,41,43,47ですが49以下なので7より小さい5でわれないか調べれば,素数ですから,35以外は全て素数です｡では49を超え7!!の210までの数では
n=9　53,55
n=10　59,61
n=11 65,67
n=12　71,73
n=13　77,79
n=14　83,85
n=15　89,91
n=16　95,97
n=17　101,103
n=18　107,109
n=19　113,115
n=20　119,121
n=21　125,127
n=22　131,133
n=23　137,139
n=24　143,145
n=25　149,151
n=26　155,157
n=27　161,163
n=28　167,169
n=29　173,175
n=30　179,181
n=31　185,187
n=32　191,193
n=33　197,199
n=34　203,205
n=35　209,211
ですが,これは,5から√210≒14.49だから,5から14に近い素数17までの素数でわれなければそれは素数です｡

この次は11!!ですが、2310のうち,11の二乗すなわち121以下の素数候補のうち11より小さい素数5と７で割れないものはそれは素数となります｡
次に,121を超えて,2311までは、√2310≒48.06だから,5から48に近い素数53までの素数でわれなければすべて素数です｡

ここで,n!!は2と3を含んでいますから6の倍数であります｡n!!±1=6m±1であるわけです。したがって,素数候補との区切りは都合がいいです｡

以上のようにn!!をnの二乗未満と超える処理をわけることで,素数表が高速にもとまるはずです｡

これの基づいてプログラムを作って見ましょう。

つづく