素数判定とエラトステネスの篩

動かして確かめる

1 本目は、1000003 の判定を 3 つの書き方で行い、割り算の回数を上の表と照らします。

全部 1000001
√nまで 999
奇数 500
√n 1000

全部で割ると 100 万回、√n までなら 999 回、奇数だけなら 500 回でした。素数のときは最後まで割り切れないので、回数は割る範囲の数と同じです。

2 本目は、篩で 100 以下の素数を全部出し、100 万以下の素数を数えます。

25 個
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
100万以下 78498
印を消した回数 2122048

100 以下の素数は 25 個で、2 から 97 までです。100 万以下の素数は 78498 個で、印を消した回数は約 212 万回、数 1 個あたり 2 回ほどでした。同じ 78498 個を 1 つずつ試し割りで見つけるより、ずっと少ない手間です。

3 本目は、試し割りを全部の数にかけた割り算の回数と、篩の印消しの回数を、N を変えて比べます。

1000 5456 1411
10000 118756 16981
100000 2755286 193078

N が 10 倍になるたびに、試し割りの合計は約 22 倍、23 倍と増えますが、篩は約 12 倍、11 倍です。N = 10 万では、試し割りの割り算の回数が篩の印消しの約 14 倍になりました。差は N が大きいほど開きます。素数をまとめて使うなら、先に篩で表を作っておくのが定石です。

4 本目は、フェルマーの小定理で判定する手と、それをすり抜ける数です。p が素数なら、p と互いに素な a について a^(p−1) を p で割った余りは 1 です。逆に、余りが 1 にならない a が 1 つでもあれば、n は合成数です。

91 False
True
互いに素な a 319
通った a 319

91 は、a = 2 で余りが 1 にならないので、合成数だと分かります。ところが 561 = 3 × 11 × 17 は、2 から 560 までの 561 と互いに素な 319 個の a の全部で余りが 1 になり、フェルマーの判定をすり抜けます。こうした合成数をカーマイケル数と呼びます。フェルマーの判定は「合成数だ」とは言い切れますが、「素数だ」とは言い切れません。

5 本目は、フェルマーの判定を強めたミラー・ラビン法です。底に最初の 12 個の素数 (2 から 37) を使うと、3.18 × 10^23 より小さい数では、判定が外れないことが分かっています。

561 False
1000003 True
1000000007 True
2305843009213693951 True
2147483662032385529 False

561 は合成数と正しく出ました。19 桁の 2^61 − 1 は、試し割りなら √n が約 15 億なので、奇数だけでも 7 億回を超える割り算が要ります。ミラー・ラビン法なら、底 12 個の分だけ繰り返し二乗法を回すだけで、一瞬で素数と分かります。2 つの素数を掛けた最後の数は、合成数と出ました。