素数について:10桁程度のINTMAX位の範囲の最速素数判定法:javascript:アルゴリズム


はじめに
素数判定法はいろいろありますが
この方法が10桁程度のINTMAX位の範囲ならば
最も高速だと思います
2*10^10の素数判定においてシンプルな√nまでの奇数の割り切り素数判定法の
計算量は√(2*10^10)=√(2)*10^5*1回のループ?処理コード量
あるいは(√(2)/3)*10^5*1回のループ?処理コード量程度になります

それは最小の素数の組み合わせが
2と3なのでそのLCMの6の倍数の±1
であることが素数の条件だということです
6で割ったとき余りが1か5ならば素数の可能性があって
余りが3は3の倍数その他の余りは2の倍数だからです
これだけで2/6=1/3に篩にかけられます

素数6の倍数の列挙(120まで)
1 2 3 5 6 7 11 12 13 17 18 19 23 24 29 30 31
36 37 41 42 43 47 48 53 54 59 60 61 66 67 71 72 73
78 79 83 84 89 90 96 97 101 102 103
107 108 109 113 114 120

多分

6の倍数の±1であるかどうかを調べること


からさらに当該数/2(詳細は後述しますが説明のため)までの列挙済みの素数で
割り切れるか調べることが最速の素数判定法です
したがって1/6に篩にかけました
重複しますが2の倍数でないことで1/2
判定数の1/2まで調べればいいことから
もっと簡易的には1/4に篩にかけました
なので113ならば最大29個具体的には
5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 57
19個の素数判定をすれば113の素数判定が可能です
もっと簡易的には
もちろんわざわざ丁寧にこの19個の素数判定をしなくても
そのまま割り切れるかどうかだけでも113の素数判定は可能です
その場合例えば99991の素数判定において最大16666回
割り切れるかどうか調べれば99991の素数判定が出来ます


計算例 113
・113%6=5であるので条件を満たす
・113/2=58までの列挙済み素数で割り切れるか判定
・113%5≠0 OK
・113%7≠0 OK
113%9≠0 OK
・113%11≠0 OK
・113%13≠0 OK
113%15≠0 OK
・113%17≠0 OK
・113%19≠0 OK
113%21≠0 OK
・113%23≠0 OK
113%25≠0 OK
113%27≠0 OK
・113%29≠0 OK
・113%31≠0 OK
113%33≠0 OK
113%35≠0 OK
・113%37≠0 OK
113%39≠0 OK
・113%41≠0 OK
・113%43≠0 OK
113%45≠0 OK
・113%47≠0 OK
113%49≠0 OK
113%51≠0 OK
・113%53≠0 OK
113%55≠0 OK
113%57≠0 OK
・113は素数である
赤字は素数列挙を用いないとき
緑字は6の余りを考えないとき

さらに素数の一般常識として
判定数がnの時n/2でもなく√nまで調べればよい
√n以上の数では絶対に割り切れない
ということがあるので
上記の議論の調べる最大値を√nとします
だからこれで(2/6)√n=(√n)/3に篩にかけたことになります
したがって10^10の素数判定の場合最大(10^5)/3回割り切れるか調べればいいことになります
で99991の素数判定は√99991=317あるいは317/3=105回割り切れるか調べればいいことになります
また高速化を意図して余計なことをすると残念ながら余計に遅くなるみたいです
だからエラトステネスの篩が速いなんてまんまと騙されていると思うのですがね
素数テーブルを用意して強引に照合しても遅いのですからね
基本的には素数列挙法はメモリを余計に食うし動作も遅いので
素直に√nまでの奇数で強引に割り切れるかどうかを調べた方が
メモリも食わないし動作も速いと思います

この議論をさらに進めて6ではなく2*3*5=30で割って
30までの2.3.5を除く素数の
1 7 11 13 17 19 23 29
に余りがなることが30以上の素数の条件なので
この場合8/30=4/15に篩にかけられるのですが
これは言うほどあまり効果がないのかもしれません
2*3*5*7とかでも43/210の篩等同様の議論ができます
確かに1/4.88に篩にかけられますが43回のif文照合があるので
凝りすぎて余計遅くなっては元も子もないので6で良いのではないでしょうか?

また
エラトステネスの篩を改良して

・n % 6 が1か5でなければ素数ではないで即終了
・2 から n までの自然数を並べる
・最小の 2 を残して 2 の倍数をすべて取り除く
・残った数の最小の 3 を残して 3 の倍数をすべて取り除く
・残った数の最小の 5 を残して 5 の倍数をすべて取り除く
・以下同様に まだ消えてない最小の数を残し その倍数をすべて取り除く
・残った数の最小が √n を超えたら残った数はすべて素数

が多分最速の素数判定アルゴリズムでしょう
と思ったんだけれどおらのエラトステネスの篩の実装方法がヘボくて余計遅かったにゃ
多分1回毎に処理をシステムに戻すせいにゃ
0.1Mまでの素数テーブルを使ってもガイドインデックスを使用しないとかの実装によっては余計遅いのかも
ガイドインデックスとは判定数までの素数の個数のおおよその数はlogなんとかで計算できるからそれを利用することでし
多分この実装だと余計なことをほとんどしていないCHECK PRIME(EASY)が最速素数判定アルゴリズム
var ONELOOPNUM = 1000;
また1回のループでフリーズ防止でシステムに制御を戻すために
計算を1000回に制限しているのでCPUの限界までは使っていません






注意:あんまり巨大な数を計算するとメモリ破壊で壊れます
100000くらいまでなら多分大丈夫
エラトステネスの篩は実装がヘボいのか大きい数は危険かも
推奨動作確認は99987(非素数) 99989(素数) 99991(素数) 99993(非素数)とかで動作確認してね
INTMAXと同じくらいの桁数の999999937(素数)の判定もCHECK PRIME(EASY)で可能です
それを他のでやると危なそうです
ちなみに999999937の素数判定は√999999937=31623あるいは31623/3=10541回の計算です


ソースコード

var TMan = new N6LTimerMan();  //タイマーマネージャー
TMan.add();


window.onload=function(){
  readCSV('./primelist100000.txt', 'analyzeCSV', 'readedCSV');
}

var PRMTABLE = [];
var READED = false;

function readedCSV(res) {
  if(res.length < 1) return;
  var i;
  for(i = 0; i < res.length; i++){
    PRMTABLE.push(parseInt(res[i]));
  }
  READED = true;
}

var PRM = [2, 3, 5];
var ONELOOPNUM = 1000;
var TMP = 7;
var NUM;
var MOD = true;
var USEMOD = 100;

function checkprime(num, max){
  if(max < PRM[PRM.length - 1]) return num;
  var i;
  var mod = num % 6;
  if((mod != 1)&&(mod != 5)) return -1;
  for(i = 2; i < PRM.length; i++){
    if(max < PRM[i]) return num;
    if(num % PRM[i] == 0) return -1;
  }
  return num;
}

function enumprime(num){
  PRM = [2, 3, 5];
  TMP = 7;
  function Loop(id){
    var cnt;
    for(cnt = 0; cnt < ONELOOPNUM; cnt++){
      if(num < TMP){
         if(checkprime(NUM, num) == NUM) {
           TXT_ANS.value = "Prime Number"
         }
         else{
          TXT_ANS.value = "Not Prime Number"
        }
        return;
      }
      var maxtmp = Math.ceil(Math.sqrt(TMP));
      if(checkprime(TMP, maxtmp) == TMP){
        PRM.push(TMP);
      }
      TMP += 2;
    }
    TMan.timer[id].setalerm(function() { Loop(id); }, 50);  //メインループ再セット
  }

  Loop(0);
}

//素数列挙あり
function oncheckprime(){
  TXT_ANS.value = "Calculating・・・"
  NUM = parseInt(TXT_NUM.value);
  var max = Math.ceil(Math.sqrt(NUM));
  if((NUM == 1)||(NUM == 2)){
    TXT_ANS.value = "Prime Number"
    return;
  }
  if((NUM <= 0)||(NUM % 2 == 0)){
    TXT_ANS.value = "Not Prime Number"
    return;
  }
  var mod = NUM % 6;
  if((NUM != 3)&&((mod != 1)&&(mod != 5))){
    TXT_ANS.value = "Not Prime Number"
    return;
  }
  enumprime(max);
}

//素数列挙なし
function oncheckprimeeasy(){
  TXT_ANS.value = "Calculating・・・"
  NUM = parseInt(TXT_NUM.value);
  MAX = Math.ceil(Math.sqrt(NUM));

  if((NUM == 1)||(NUM == 2)||(NUM == 3)){
    TXT_ANS.value = "Prime Number"
    return;
  }
  if((NUM <= 0)||(NUM % 2 == 0)){
    TXT_ANS.value = "Not Prime Number"
    return;
  }

  TMP = 5;

  var mod = NUM % 6;
  if((NUM != 3)&&((mod != 1)&&(mod != 5))){
    TXT_ANS.value = "Not Prime Number"
    return;
  }

  if(MAX <= TMP){
     TXT_ANS.value = "Prime Number"
     return;
  }

  function Loop2(id){
    var cnt;
    for(cnt = 0; cnt < ONELOOPNUM; cnt++){
//      if((MOD)||(USEMOD <= TMP)){
        mod = TMP % 6;
        if((mod != 1)&&(mod != 5)){
          TMP += 2;
          continue;
        }
//      }
      if(NUM % TMP == 0){
        TXT_ANS.value = "Not Prime Number"
        return;
      }

      TMP += 2;

      if(MAX <= TMP){
         TXT_ANS.value = "Prime Number"
         return;
      }
    }

    TMan.timer[id].setalerm(function() { Loop2(id); }, 50);  //メインループ再セット
  }

  Loop2(0);
}


function onEratosthenes(){
  TXT_ANS.value = "Calculating・・・"
  NUM = parseInt(TXT_NUM.value);
  MAX = Math.ceil(Math.sqrt(NUM));
  if(200000 <= NUM){
    TXT_ANS.value = "Do not number range!!!"
    return;
  }
  if((NUM == 1)||(NUM == 2)||(NUM == 3)){
    TXT_ANS.value = "Prime Number"
    return;
  }
  if((NUM <= 0)||(NUM % 2 == 0)){
    TXT_ANS.value = "Not Prime Number"
    return;
  }
  var mod = NUM % 6;
  if((NUM != 3)&&((mod != 1)&&(mod != 5))){
    TXT_ANS.value = "Not Prime Number"
    return;
  }

  var i;
  PRM = [2];
  for(i = 3; i <= NUM;){
    PRM.push(i);
    i += 2;
  }

  TMP = 1;
  function Loop3(id){
    var cnt;
    for(cnt = 0; cnt < ONELOOPPROC; cnt++){
      if(MAX <= PRM[TMP]){
        if(PRM[PRM.length - 1] == NUM){
          TXT_ANS.value = "Prime Number"
          return;
        }
        else{
          TXT_ANS.value = "Not Prime Number"
          return;
        }
        TMP++;
      }

      TXT_ANS.value = "Calculating・・・" + PRM[TMP];

      var tmp;
      var n;
      for(tmp = TMP; tmp < PRM.length; tmp++){
        var tprm = PRM.filter(n => ((n === PRM[tmp])||(n % PRM[tmp]) !== 0));
        PRM = [];
        PRM = [...tprm];
      }
    }

    TMan.timer[id].setalerm(function() { Loop3(id); }, 50);  //メインループ再セット
  }

  Loop3(0);

}

function onTable(){
  if(!READED) {
    TXT_ANS.value = "Do not read yet!!!"
    return;
  }
  TXT_ANS.value = "Calculating・・・"
  NUM = parseInt(TXT_NUM.value);
  MAX = Math.ceil(Math.sqrt(NUM));
  if(100000 <= NUM){
    TXT_ANS.value = "Do not number range!!!"
    return;
  }
  if((NUM == 1)||(NUM == 2)||(NUM == 3)){
    TXT_ANS.value = "Prime Number"
    return;
  }
  if((NUM <= 0)||(NUM % 2 == 0)){
    TXT_ANS.value = "Not Prime Number"
    return;
  }
  var mod = NUM % 6;
  if((NUM != 3)&&((mod != 1)&&(mod != 5))){
    TXT_ANS.value = "Not Prime Number"
    return;
  }

  TMP = 0;
  function Loop4(id){
    TXT_ANS.value = "Calculating・・・" + PRMTABLE[TMP];
    var i;
    for(i = 0; i < ONELOOPNUM; i++){
      if(NUM < PRMTABLE[TMP + i]){
        TXT_ANS.value = "Not Prime Number"
        return;
      }
      if(PRMTABLE[TMP + i] == NUM){
        TXT_ANS.value = "Prime Number"
        return;
      }
    }

    TMP = TMP + i + 1;

    TMan.timer[id].setalerm(function() { Loop4(id); }, 50);  //メインループ再セット
  }

  Loop4(0);
}

function onCHK(){
  MOD = CB_CHK.checked;
}



注意
判定する数があまり大きな数でないのならば
mod = TMP % 6;
if((mod != 1)&&(mod != 5)){
 TMP += 2;
 continue;
}
など6で割って余りが1か5の判定は
簡易判定の計算が余計になるので
あまり効果を発揮しません
例えば
99993%6=3
で1か5でないので素数ではない
と1回余りを求めてはじくときに効果を発揮します
ですので判定する数が大きな数でないと多分冗長でしょう
CHECK PRIME(EASY)でmod6を使うかどうか判定していますけれど
if文判定なんてしないで強制的に毎回使ったほうが多分速いです
だからコメントアウトしました


まとめ:最速素数判定アルゴリズム


・√nまでの3以上の奇数xでn mod x がゼロならば素数でないそしてすべてクリアしたらnは素数である
・また6以上のy mod 6が1か5ならばyが素数の可能性がある簡易判定法だからnやxが素数の可能性がないのならば計算を省略できる
・おまけにフリーズ対策である程度計算したらシステムに制御を戻すとプログラムとして素晴らしい





N6LIsPrime()使用法



CHECK PRIME(EASY)をNAS6LIBにカプセル化した以下使用方法

<script language="JavaScript" type="text/javascript" src="./javascripts/nas6lib/common.js"></script>
<script language="JavaScript" type="text/javascript" src="./javascripts/nas6lib/timer.js"></script>
<script language="JavaScript" type="text/javascript" src="./javascripts/nas6lib/prime.js"></script>
を宣言する

関数は
//入力////////////////////////////////////////////////
//id : TManのid
//num : 判定する数
//出力////////////////////////////////////////////////
//num : 素数である
//-1 : 素数でない
//0 : 計算継続中
//////////////////////////////////////////////////////
function N6LIsPrime(id, num);
となっています

注意
N6LIsPrime()が内部で使用するタイマーと
N6LISPRMRETの戻り値を監視するタイマーの
2つのタイマーが必要です


テストコード

var TMan = new N6LTimerMan();  //タイマーマネージャー
TMan.add();
TMan.add();

...省略...

function onN6LIsPrime(){
  TXT_ANS_T.value = "Calculating・・・"
  NUM = parseInt(TXT_NUM_T.value);
  var ret = N6LIsPrime(0, NUM);

  function Loop5(id){
    if(ret == NUM){
      TXT_ANS_T.value = "Prime Number"
      return;
    }
    else if(ret < 0){
      TXT_ANS_T.value = "Not Prime Number"
      return;
    }
    ret = N6LISPRMRET;
    TMan.timer[id].setalerm(function() { Loop5(id); }, 75);  //メインループ再セット
  }

  Loop5(1);
}
}







function IsPrime(num){
  if((num == 1)||(num == 2)||(num == 3)) return num;
///////////////////#1
  var mod = num % 6;
  if((mod != 1)&&(mod != 5)){
    return -1;
  }
///////////////////
  var max = Math.floor(Math.sqrt(num));
  var tmp;
  for(tmp = 5; max < tmp;){
///////////////////#2
    mod = tmp % 6;
    if((mod != 1)&&(mod != 5)){
      tmp += 2;
      continue;
    }
///////////////////
    if(num % tmp == 0){
      return -1;
    }
    tmp += 2;
  }
  return num;
}



numが与えられて素数判定(戻り値num:素数-1:非素数)をするプログラムで
#2は冗長かもしれませんが
#1はかなり有効な高速化だと思います


エラトステネスの篩javascript


function IsPrimeEratosthenes(num){
  if((num == 1)||(num == 2)||(num == 3)) return num;
  var mod = num % 6;
  if((mod != 1)&&(mod != 5)){
    return -1;
  }
  var max = Math.floor(Math.sqrt(num));
  var i;
  var PRM = [2];
  for(i = 3; i <= num;){
    PRM.push(i);
    i += 2;
  }
  var TMP;
  for(TMP = 1; PRM[TMP] <= max; TMP++){
    if(max < PRM[TMP]){
      if(PRM[PRM.length - 1] == num){
        return num;
      }
      else{
        return -1;
      }
    var tmp;
    var n;
    for(tmp = TMP; tmp < PRM.length; tmp++){
      var tprm = PRM.filter(n => ((n === PRM[tmp])||(n % PRM[tmp]) !== 0));
      PRM = [];
      PRM = [...tprm];
    }
  }
  return num;
}






戻る