JavaScriptで素数 #JavaScript

参照記事：
99 Haskell Problems より、[31] でもその前に
 Haskellで素数 2 自分でもやってみた。
Pythonで素数 2 Pythonでやってみた。 ~~この記事はこれの改良版です。~~ 改良になってなかった。Python版と同じに戻しました。
~~Javascript: スプレッド構文とジェネレーターを使ってtransducerっぽいことをするジェネレーター関連のこと。~~ 本題からずれて無駄に難しくなるので、関数合成関連のコードは削除しました。

Haskell界隈でやられている方法を以前教えていただいたので、JavaScriptでどうできるか、やってみました。
理屈はめんどくさいですが、何かと効率がいいようです。

letとかwhileとか使いまくりで、何が関数型か?思いっきり手続き型じゃない?という感じですが、Haskellの遅延評価を使ったクールなコードを、何とかJavaScriptのジェネレーターで実現しようとした爪痕です。
暖かい眼で見てやってください。

//最大公約数。
const gcd = x => y => y === 0 ? x : gcd( y )( x % y )

// 配列をジェネレーターにする。
const arrayToG = xs => function*(){
    yield* xs;
}();

//ジェネレーターg1にg2を継ぎ足したジェネレーターを返す。
const chain = g1 => g2 =>function*(){
  yield* g1;
  yield* g2;
}();

// 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 未満の素数を全てかけた数、
// sに 6*n+1 型の自然数、pに素数をとって、
//s から p*p-2 までの素数を返すジェネレーター。
const zonedPrimes = m => s => p => function*(){
  const nG = croppedPrimables(s)(p);
  let x;
  while(!( x = nG.next()).done ){
    if(gcd(m)(x.value) === 1)yield x.value;
  }
}();

//素数を返すジェネレーター。
const primes = () => function*(){
  let x;
  let primeG = arrayToG([2, 3, 5]);
  let [m, s, p] = [1, 7, 5];

  let seedG = arrayToG([]);

  while(true){
    while( !( x = primeG.next() ).done ) yield x.value;
    primeG = zonedPrimes(m)(s)(p);
    seedG = chain(seedG)(zonedPrimes(m)(s)(p));
    [m, s, p] = [ m * p , p * p , seedG.next().value ];
  }
}();

//100以下の素数を表示する。
{
  const primesGen = primes();
  let x;
  while((x = primesGen.next()).value <= 100) console.log(x.value);
}
//=>結果
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

仕組み

ジェネレーター croppedPrimable は：

引数sに6n+1型の整数をとることで
p^2-2 までの2と3の倍数を除いた素数候補を、
呼ばれるたびに一個ずつ返します。

なんでわざわざこんなことを?とも思うのですが、次の素数を選別する処理が重くてロスが大きいので、なるべく候補を絞って効率良く、ということなのでしょうたぶん。

ジェネレーター zonedPrimes は：

croppedPrimables(s)(p)から一個ずつ値をとり
mとの最大公約数が1になる値を一個ずつ返します。

mには、最初は1、その後、2,3を除いたp未満の素数(5,7,11...)を全てかけた数がはいります。

ジェネレーターprimesは呼ばれるたびに素数を一個ずつ返します。
内部にふたつのジェネレーターがあります。

primeG(初期値[2,3,5]):外部に素数を返す用
seedG(初期値[]):内部でprimeG の再充填に使う p を供給する用

ふたつとも素数を返すジェネレーターに違いはありませんが、値を消費する速度がだいぶ違います。
このふたつを使ってhaskellの遅延評価の部分をなんとか実現しようとしています。

primeGが素数を一個ずつ返し、
primeGが空になったら、zonedPrimes(m)(s)(p)でprimeGを再充填する
seedGの後ろにzonedPrimes(m)(s)(p)を継ぎ足す。
primeGの再充填のためのパラメータ m, s, p を再設定する

という流れです。

いい考えだと思ったんだけど...
だめでした。2207以下だったらいいんだけど、それ以降になるとおかしくなってしまう...

残念! この方法では2207までしか計算できない...

教えていただいたHaskellのコード(ちょっとだけ簡単にしてある)で2207の次の素数を求めてみました。

Haskell

primes::Integral a => [a]
primes = [2, 3] ++ primes'
    where
      primes' = [5] ++ f 1 7 primes'
      f m s (p : ps) = [n | n <- ns, gcd m n == 1] ++ f (m * p) (p * p) ps
          where ns = [x + y | x <- [s, s + 6 .. p * p - 2], y <- [0, 4]]

main = print . take 1 . dropWhile(<=2207) $ primes

-- 結果：
[2213]  -- 正しい

上で作ったJavaScriptのジェネレーターprimesを使って、同様に2207の次の素数を求めてみました。

JavaScript

{
    const primesGen = primes(); 
    let x; 
    while( (x = primesGen.next().value)<=2207); 
    console.log(x); 
}
=>2209  // = 47*47 正しくない

理由は、gcdを計算するための m が素数を順にかけていく内にどんどん大きくなってNumber.MAX_SAFE_INTEGERを越えてしまうからでした。

Number.MAX_SAFE_INTEGER
=> 9007199254740991

5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43
// Haskell:
=> 2180460221945005 // 正しい
// JavaScript:
=> 2180460221945005 //  Number.MAX_SAFE_INTEGER以下。 正しい

5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47
// Haskell:
=> 102481630431415235 //  正しい
// JavaScript:
=> 102481630431415230 // Number.MAX_SAFE_INTEGERを超えている。正しくない

なんとか解決する方法を考えてみました。
JavaScriptで素数 2