Javascriptでの整数nまでの素数を数えるアルゴリズムについて

Question

###素数計算をより高速処理をする為に

仕事時間の合間や休みの日に勉強がてら簡単なプログラムを作ったりしているのですが、
最近、素数の数を数えるプログラムをJavacriptで組みました。

様々な方法でアルゴリズムを組み、それぞれの計算速度を比較して楽しんでいますが、
より高速に処理をこなせるアルゴリズムを探しています。

素数判定の様々な計算方法は調べてみたのですが、
数学知識が乏しく理解できるものが少ないというのが現状です。
ここをこうすると速くなる、そもそもこういうアルゴリズムの方がいい！
など、皆さまの知識を吸収させていただきたく、質問させていただいきました。

###処理の内容

整数n以下の全ての素数の数を数える

###現在の実装

function PrimeCalculater(op){ //この関数はクリックイベントで呼び出されます
  let max_value = parseInt($('input.form_value').val()); //Webページ側から整数nとなる値を取得します
  let primeArr = new Array(); //素数格納用配列
  let cal_counter = 0; //計算回数カウンタ
  primeArr.push(2,3,5,7); //Webページ側で最小値10と設定しているので、10以下の素数はあらかじめ用意します

  const startTime = performance.now(); //測定用

  for(i=11; i<max_value; i+=2){ //偶数は省く
    let status = true;
    for(j=1; (primeArr[j]<parseInt(Math.sqrt(i))+1) && j<primeArr.length && status; j++){ //primeArr[0] = 2 なので省く
      cal_counter++;
      if((i % primeArr[j]) == 0) status = false; //割り切れたら処理を中断し次の検査値へ
    }
    if(status) {
      primeArr.push(i);
    }
  }

  //Webページに結果を出力
  $('td.cal').text(((performance.now() - startTime)/1000).toFixed(12) + ' 秒');
  $('td.counter').text(cal_counter.toLocaleString() + ' 回');
  $('td.answer').text((primeArr.length).toLocaleString() + ' 個');
}

いくつか作成したアルゴリズムの中で最速のものが上記のコードでした。
もちろん、演算回数をカウントする部分を無くしたらもう少し早くなると思いますが…。

Webサイト側では 10～999,999,999 の整数が入力できるフォームがあり、
そこに数値を入力し、実行ボタンを押すことで計算を開始し、結果をサイト上に表示する仕組みです。
（実際はその他の計算方法が選択できる構造になっています）

処理としては、Web側で指定された整数に対して、11～指定値までの奇数を順番に素数判定していきます。
判定方法ですが、判定する素数の平方根（小数点切り捨て）+1 の値までに存在する素数のみで
割り切れるかどうかで素数かどうかを判断し、途中で割り切れれば処理を中断し次の値のチェックに移行します。
素数だった場合は素数リストにその値を追加していきます。
これを指定数まで繰り返していきます。

最終的にその配列の要素数を出力するという仕組みです。

###計算速度
この実装で1億までの素数の数を数えさせた結果は画像の通りです。

これ以外だと…

1000万の場合は 約3.2秒
100万の場合は 約0.14秒
10万の場合は 約0.01秒

というような計算速度です。
（PC依存の速度なので環境によってだいぶ違うとは思います）

###やりたいこと・知りたいこと
この実装、またはこれ以外のアルゴリズムでより早い計算方法を知りたいです。
自分の解法ではこの速度が限界でした。ご鞭撻のほどお願いいたします。

###追記
具体的には1億以上の数値が入力された場合の演算を高速化したいと考えています。

###2020/08/25 追記（エラトステネスの篩実装）
ご助言頂きましたエラトステネスの篩による実装です。

//max_valueにはフォームからの入力値が入ります
//ここでmax_valueの値が1億などとされるとこの実装ではmemory outし、ページが停止します。
let prime = new Array(max_value).fill(true);

//primeCounterは本来必要ありませんが、最終的に配列の要素数 = 素数の数としてWebページに出力する都合上、
//素数の数をカウントしてその大きさの配列を作る為に使用しています
let primeCounter = 0;

prime[0] = false;
prime[1] = false;

for(let i = 2; i <= maxSqrt; i++) { //maxSqrt には parseInt(Math.sqrt(max_value))+1 が代入されています
  if(prime[i]) {
    for(let j = i * 2; j <= max_value; j += i) {
      cal_counter++; //この変数は別の場所で宣言しており、演算回数を図る為のものです
      prime[j] = false;
    }
  }
}
for(let i = 0; i < prime.length; i++) {
  cal_counter++;
  if(prime[i]) primeCounter++;
}

primeArr = new Array(primeCounter);

エラトステネスの篩に関係のない部分は省略しています。
エラトステネスの篩というものの解釈がこれであっているのか自信はありませんが、
設定された整数と同一の数の配列を宣言し、その中身を一度全て TRUE としておきます。
それから 0 と 1 は素数ではないので手動で FALSE を代入します。
繰り返しを 2 からスタートし、ネストしたループ処理でその倍数となる要素を全て FALSE にしていきます。
ループ処理の際、その要素が既に篩に掛けられ素数ではない判定(FALSE)になっている場合は次へ移行します。
この処理を parseInt(Math.sqrt(max_value))+1 以下まで繰り返します。

最後に配列内で TRUE となっている要素の数を数えればそれが素数の数になっているはず、

という実装です。

この実装によって得られた結果は以下の画像の通りです。

Answer 1

エラトステネスの篩、という古代ギリシャから伝わるアルゴリズムがあります。

詳細は検索すればすぐヒットしますので省略しますが、割り算も不要で、（メモリ容量が十分確保できるなら）高速に処理できます。

Comments

[phiar_poet]

ご回答ありがとうございます。
メモリ容量が十分に確保できるなら、がネックなんですよね…。
エラトステネスの篩については調べました。

その実装に伴って最初に整数nまでの配列を作成するという内容だったのですが、
ブラウザの仕様上、例えば要素の数が1億の配列を宣言できるかと言われるとNoで、
ブラウザで動かすJavascriptでの実装が難しかったので度外視していました。

他の言語等では要素数1億の配列の宣言など、一般的なメモリ容量上現実的な数字なのでしょうか…。

[maisumakun]

工夫すれば、要素数1億まで行かなくても処理できます。

・まず、1億の平方根である1万まででふつうにエラトステネスの篩を行って、1万までの素数リストを出しておく
・1～100万の100万個の配列を用意して、1万までの素数で消して、素数を洗い出す
・次は100万+1～200万で行う（消すのは1万以下の素数だけで問題なし）
・以下、1億まで順次進めていく

というように分割して行うことも可能です。

[phiar_poet]

分割して処理を行うというのは盲点でした…。
こういうところの発想の転換が自分には足りないようです。

まず、あれからエラトステネスの篩を素直に実装したところ、
30,000,000程度であれば処理できました。
（40,000,000を宣言した際には急激に遅くなったのでメモリがギリギリなのかもしれません）

余談ですが、入力値が30,000,000の時に既存の計算方法では

計算時間: 7.875954999821 秒
演算回数: 1,636,119,415 回

だったのに対し、エラトステネスの篩による演算結果では

計算時間: 0.653870000038 秒
演算回数: 102,463,862 回

というかなりの高速化が図れました。
ありがとうございます。

なお 30,000,000 までに存在する素数の数は 1,857,859 個 のようでした。

分割して1億以上の処理ができるよう、もう少し考えてみます。

[yambejp]

phiar_poetさん

> エラトステネスの篩を素直に実装

ちなみにどういった実装でしょうか？
分割は結局２から順に処理しないといけないので
あまり意味がないかもしれません

[phiar_poet]

yambejp様

お返事いただきましてありがとうございます。
実際に実装したコードを質問内容に追記しました。
ご確認いただければと思います。

分割についてはとりあえずコードを書いてみて速度チェックはしてみたいと思っています！
何分、知識が乏しいものなのでとりあえずコードを書いていろいろ試してみる、を実践しているところです…。

Answer 2

いろいろやってみましたがエラトステネスの篩を分割で処理させる
というコードはうまく実装できませんでした…。
とりあえず、なんとか計算方法を早くしようとした結果邪道かもしれませんが
次の方法で決着しました（させました…）。

実装

var cal_counter = 0;
var PRIME_MEM = [...]; //この配列には10,000,000までの素数が入っています

function calculateStart(op){ //サイト側の計算開始ボタンで実行されます

    let max_value = parseInt($('input.form_value').val()); //このDOM要素に計算した数値が入っています
    let primeArr;
    let primeCounter;
    let index = PRIME_MEM.indexOf(max_value);

    const startTime = performance.now(); //計算開始時間を取得

        //10,000,000までの素数表があるので検索値以下の最大の素数を検索します
        //その最大の素数が登録されているindex番号+1が素数の数となるはず
    if(max_value <= 10000000){
      for(let i = max_value - 1; index == -1; i--){
        cal_counter++;
        index = PRIME_MEM.indexOf(i);
      }
      primeCounter = index + 1;
    } else { //検索値が10,000,000よりも大きければそこからは試し割り算
      primeCounter = PRIME_MEM.length;
      for(let i = 10000001; i <= max_value; i++){
        if(isPrime(i)) primeCounter++;
      }
    }

        //配列を宣言する必要はないがここには記載していない他の計算方法との出力の兼ね合い
    primeArr = new Array(primeCounter);

        //出力
    $('td.cal').text(((performance.now() - startTime)/1000).toFixed(12) + ' 秒');
    $('td.counter').text(cal_counter.toLocaleString() + ' 回');
    $('td.answer').text((primeArr.length).toLocaleString() + ' 個');

        //cal_counter は var で宣言している為、値を初期化
    cal_counter = 0;
}

    //試し割り算を行う関数
function isPrime(n){
    let maxSqrt = Math.sqrt(n); //試し割り算を繰り返す最大値

    for(let i = 0; PRIME_MEM[i] <= maxSqrt; i++){
      cal_counter++;
      if(n % PRIME_MEM[i] == 0){ //素数で割り切れた時点でFALSEを返す
        return false;
      }
    }
    return true;
}

###概要

10,000,000までの素数を事前に用意してみる、という実装にしました。
10,000,000以下と10,000,001以上で当然計算方法が異なります。

10,000,000以下の場合はその数値以下の最大の素数を素数表から探し出し、
そのINDEX番号+1が素数の数となる、という計算方法で導き出します。
当たり前ですが、こと10,000,000以下、または10,000,000付近の答えを導き出す場合は
エラトステネスの篩より高速です。

10,000,001以上については試し割り算を行って素数を探していきます。
その際は、素数表の長さプラスそこからの素数の数となるのでそのように実装しています。

###演算結果

およそ40%ほど計算時間を短縮しました。（元々は77.2秒）

他の数値を入力した場合の計算結果は次の通りです。
大小ランダムな数値を突っ込みます。

入力値	最初の試し割り算	エラトステネスの篩	今回の計算方法	素数の数
2,675	0.00010秒	0.00005秒	0.00212秒	387種類
68,392	0.04201秒	0.00096秒	0.00164秒	6,801種類
284,768	0.01984秒	0.00360秒	0.00487秒	24,825種類
1,873,649	0.22580秒	0.02433秒	0.00694秒	140,206種類
9,837,561	1.93935秒	0.20176秒	0.00359秒	654,606種類
10,574,823	3.40969秒	0.22342秒	0.12017秒	700,241種類
29,485,734	16.71694秒	0.67303秒	4.92683秒	1,827,874種類
100,000,000	76.98432秒	メモリ不足	44.97676秒	5,761,455種類

様々な数値を試してみましたが、素数表を用意した今回の計算方法では、
10,000,000以下の数値に関してはどのような数値が来ても0.001秒～0.007秒処理が行えるようで、
素数表に含まれている数値以下であるならおよそ数値の大小関係なくこの速度が出るということでした。
（検索値以下の最大素数までに何回デクリメントを繰り返すかで処理時間が変化するだけなので検索値の大小で差は生まれにくい）

ただし、入力値が計算数と速度に常に影響する最初の計算方法やエラトステネスの篩については、
入力値が小さければ小さいほど速度が速くなるので今回の計算方法よりも早いという結果です。

10,000,000までの素数表を事前に用意しておく計算方法では、
1,000,000～11,000,000の間で事前に素数表を用意した計算方法が早く、
それ以外ではエラトステネスの篩が最速、という形です。

エラトステネスの篩すごいな……。
メモリさえ足りれば巨大な数値が入ってきてもエラトステネスの篩が最速というのが答えとなりそうです。

お付き合いいただきました方、ありがとうございました！