素数判定プログラム

概要

2005/04/23

素数とは、2,3,5,7,11,13,17のように、1と自分自身でしか割り切れない数を言う。別の定義では約数が2つしかない数、約数とは割り切れる数である。この定義では、1の約数は1つしかないので素数ではない。この素数を小さい順に列挙するプログラムについて考える。

エラトステネスのふるい

2005/04/23

今回のプログラムでは、最も一般的なエラトステネスのふるいを用いて素数判定を行う。ちなみに、大きな素数を判定する方法としてフェルマーの小定理があるが、小さな素数を判定することには不向きだ。この方法を利用し、大きな桁数の素数を判定するものは素数判定プログラム(2)で取り上げる。

エラトステネスのふるいは、既に判明している素数で次々とその素数よりも数を割っていき、素数を判定していくものだ。手動でやる場合は単に合成数を削っていくより、表にしたほうが効率的である。以下は自然数を6行ごとに並べた表。

表にすると2の倍数や3の倍数を1列まるごと消すことが出来る。残った行は、表の上のほうで判明している小さい素数を使い他の数が割り切れるかどうかを繰り返し計算することで素数を判別できる。

この結果より2,3を除き全ての素数は6x+1か6x+5で表せることが分かる。これから、2より大きいの全ての奇数を配列にしてエラトステネスを行うより、6x+1又は6x+5で表される数だけを判定したほうが効率いいことが分かる。

素数判定プログラム(JavaScript)

2005/06/14

先の6行エラトステネスの表から、JavaScriptによるプログラムを用意した。実行できるプログラムは2種類あり、一方は予め判定したい数までの配列を作り、配列を徐々に削ることで候補を絞る、エラトステネス法。もう一方は小さな数から順番に、その数より小さな自然数でひたすら割りまくる総当り法だ。

現在は、この2つの利点を生かして遥かに高速化されたものがある(更に下を参照)。

さらに高速化された素数判定プログラム

2005/09/17-2005/11/18

判明済みの素数の配列を作り、候補である6x+1又は6x+5で表される数を先の配列の素数で割ることで判定する。候補が素数だと分かれば、判明済みの素数の配列に加え、作業を繰り返す。

var max = 10000;//最高値
var prime_list = new Array(2,3,5);//判明済みリスト
var x1,x2;
var i;
var count = 0;
while(true)
{
        count++;
        x1 = 6*count+1;//候補x1
        x2 = x1+4;//候補x2
        
        //候補x1の素数判定
        if( x1>max )break;//最高値より大きいなら終了
        for(i=0; i<prime_list.length; i++)//判明済み素数で次々に割る
        {
                if( prime_list[i]>Math.sqrt(x1) )//平方根の値を超えたなら素数と認定
                {
                        prime_list.push(x1);
                        break;
                }
                if(x1%prime_list[i]==0)break;//判明済み素数で割り切れるかテスト
        }
        
        //候補x2の素数判定
        if( x2>max )break;//最高値より大きいなら終了
        for(i=0; i<prime_list.length; i++)//判明済み素数で次々に割る
        {
                if( prime_list[i]>Math.sqrt(x2) )//平方根の値を超えたなら素数と認定
                {
                        prime_list.push(x2);
                        break;
                }
                if(x2%prime_list[i]==0)break;//判明済み素数で割り切れるかテスト
        }
}

素数表

2005/09/17-2005/11/18

最初のプログラムでは100秒で10万以下しかリストアップできなかったが、高速化した下のプログラムでは100秒で100万 30秒で100万までの全素数のリストアップに成功した。

• 100万以下の素数表

(2005/11/18)高速化されたJavaScriptを用いて500万以下の素数を288秒でリストアップできた。

(2008/11/19)より高速なブラウザで1000万以下の素数を258秒でリストアップできた。

• 1000万以下の素数表

多行エラトステネス法での効率について

2011/03/17

6行エラトステネスのふるいを更に拡張し、30行エラトステネスのふるいを考えることで素数の候補を更に絞ることができる。以下に30行エラトステネスの表を示す。

以上より、すべての素数は30の倍数に、2,3,5を除く30以下の素数又は1を足すことで表せることがわかる。6行エラトステネスで自然数全体を2/6まで絞り込むことができたが、30行では8/30となりわずかに効率が良い。

n行エラトステネスのふるいにおけるnは指定以下の素数の総積を入れる。6行では6=2*3、30行では30=2*3*5である。n=30のとき、自然数全体は30x+pで表され、pには2,3,5の倍数ではない値、つまり30以下の2,3,5を除く素数と1を入れることになる。逆にこれ以外の30以下のあらゆる数は2,3,5の倍数である。何故なら、2,3,5の倍数ではない最小の合成数は7*7=49だからだ。

また、nに素数積を使うn行エラトステネスのふるいにおいて、pが単純なものはn=30までである。n=2*3*5*7=210では、2,3,5,7の倍数ではない最小の合成数は11*11=121でnより小さい。よって、210x+pでは、最早pに210以下の素数を指定するだけでは足りず、2,3,5,7の倍数ではない210未満の合成数も含めなければいけない。その数は11*11,11*13,11*17,11*19,13*13の5つで、pの総数は48個、48/210まで絞り込むことができる。

更に大きなnについて、絞り込める効率を列挙した表を示す。

2*3*5*7*11*13*17*19=9699690行エラトステネスのふるいでは、nx+p式で自然数全体の17％まで素数の候補を絞り込める。これは6行エラトステネスの2倍以上の絞り込み度である。一般的に素数mまでの全素数の積nのとき、pの数はmより大きくnより小さな全ての素数の総数と、それらの素数を任意にかけ合わせてnを超えない合成数の総数に等しい。