JavaScriptで素数 2


参照記事：
[99 Haskell Problems より、[31] でもその前に](https://qiita.com/bra_cat_ket/items/6a99a9b01682886607d0)
[Haskellで素数 2](https://qiita.com/ttatsf/items/db25c4f043e1e529a7e3) 自分でもやってみた。
[Pythonで素数 2](https://qiita.com/ttatsf/items/da3bc1a26740d63586b4) Pythonでやってみた。
[JavaScriptで素数](https://qiita.com/ttatsf/items/ad2e69e8c4d5565601d9) あんまり芳しくなかった前回。

# [前記事](https://qiita.com/ttatsf/items/ad2e69e8c4d5565601d9)のまとめとこの記事の目的

[Haskell界隈の方法](https://qiita.com/bra_cat_ket/items/6a99a9b01682886607d0)をまねしてやってみたら、効率はよさげだったが、2207までしか求められなかった。
この記事では、もっと大きい素数まで効率よく求められるようにします。



# JavaScriptでまねしたHaskell界隈のやりかた
をざっくり説明すると、

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

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

この m が意外とはやく[MAX_SAFE_INTEGER](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Number/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終了時に次回の引数を返すようにしました。




```js:
//最大公約数。
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時と全然違うものを返すのでちょっと変な感じ。