参照記事：
99 Haskell Problems より、[31] でもその前に
 Haskellで素数 2 自分でもやってみた。
Pythonで素数 2 Pythonでやってみた。
JavaScriptで素数あんまり芳しくなかった前回。

前記事のまとめとこの記事の目的

Haskell界隈の方法をまねしてやってみたら、効率はよさげだったが、2207までしか求められなかった。
この記事では、もっと大きい素数まで効率よく求められるようにします。

JavaScriptでまねしたHaskell界隈のやりかた

をざっくり説明すると、

ある素数pとその次の素数qと
p以下の2、3以外の素数をすべて掛けた数mを使って
p*p から q*q-2 までの 2、3の倍数を除いた素数の候補から
mとの最大公約数が1になる数を素数とする

という処理を繰り返し行なっています。

この m が意外とはやくMAX_SAFE_INTEGER に達してしまって、以降、正確に計算できなくなってしまいました。

ちょっと工夫してみた。

変更点 1

m を単一の整数値でなく、MAX_SAFE_INTEGER 以下の数で因数分解した配列にする。
そうすればMAX_SAFE_INTEGERを超える数も正しく計算できるし、素数の判定も m の全ての要素について最大公約数が1になるか、で簡単に判定することができます。

変更点 2

一回目のzonedPrimesで 7 から 23 までの素数がわかりますが、次の回を 5*5 = 25 から 7*7ー2 = 47 までではなく、最後に求められた 23 を使って一気に
23*23ー2 = 527までいってしまおう、という作戦。
引数の _m を使うとかなりオーバーヘッドがあるものの、変更なしの簡単なアルゴリズムでいける。
求められた素数を使って zonedPrimes 内で次回分の m を更新するようにします。

変更点 3

arrayToG,zonedPrimes終了時に次回の引数を返すようにしました。

//最大公約数。
const gcd = x => y => y === 0 ? x : gcd( y )( x % y )
// xsのすべての要素とyがたがいに素
const isPrimeToEveryElement = xs => y => xs.every(e=>gcd(e)(y)===1)

// xsを破壊的に変更する。
//  xsの最後の要素と x をかけて MAX_SAFE_INTEGER以下ならそれをxsの最後の要素にする
//  でなければ、x を xs に追加
const destructivelyAddFactor = xs => x => {
  const y = xs[ xs.length - 1 ] * x;
  if( y <= Number.MAX_SAFE_INTEGER ) 
          xs[ xs.length - 1 ] = y;
        else 
          xs.push( x );
}


// 配列をジェネレーターにする。終了時にzonedPrimesの引数を返す
const arrayToG = xs => function*(){
    yield* xs;
    return {m: [5], s: 7, p: 5};
}();

// sに 6*n+1 型の自然数、pに素数をとって、
// s から p*p-2 までの2と3の倍数を除いた素数の候補を返すジェネレーター。
const croppedPrimables = s => p => function*(){
  let x = s;
  while(x <= p * p - 2 ){
    yield x;
    yield x = x + 4;
    x = x + 2;
  }
}();

// _m : 2,3 以外の p 以下の素数を全てかけた数を
//    MAX_SAFE_INTEGER以下の因数に分解して配列にしたもの
// sに 6*n+1 型の自然数、pに素数をとって、
// s から p*p-2 までの素数を返すジェネレーターを返すクロージャ。
//ジェネレーターは終了時に次回の引数 を返す
const zonedPrimes = _m =>  s => p => {
  let m =[ ..._m ];
  return function*(){
    const nG = croppedPrimables( s )( p );
    let nextNominee;
    let lastYielded;
    while( !( nextNominee = nG.next() ).done ){
      if(isPrimeToEveryElement( _m )( nextNominee.value ) ){
        yield ( lastYielded = nextNominee.value );
        destructivelyAddFactor( m )( lastYielded );
      }
    }
    return { m : m, s : p * p, p : lastYielded };
  }();
}

//素数を返すジェネレーター。返り値が MAX_SAFE_INTEGER に逹したら終了する。
const primes = () => function*(){
  let x;
  let primeG = arrayToG([2, 3, 5]);

  while(true){
    while( !( x = primeG.next() ).done ) {
      if(x.value > Number.MAX_SAFE_INTEGER) return;
      yield   x.value;
    }
    primeG = zonedPrimes( x.value.m )( x.value.s )( x.value.p );
  }
}();

// 2207の次の素数。前回NGだったやつ。
{ 
    const primesGen = primes();  
    let x;  
    while( ( x = primesGen.next().value ) <= 2207 );  
    console.log(x);  
}

//=>
2213    // 正しい。

できたー。
もっと大きい数もいけます。
環境のtimeOutにもよりますが、数万~十数万までは求められました。

まとめ

何か前記事のよりもさらに速い様子。
単純な試し割りの10倍くらいは速い雰囲気。正確にはどうなんでしょう?

ジェネレータの終了時に return で値を返すというのをやってみたら、便利だったけど謎度は深まったかも。
yield時とreturn時と全然違うものを返すのでちょっと変な感じ。

JavaScriptで素数 2