JavaScriptで素数

参照記事：
[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でやってみた。 ~~この記事はこれの改良版です。~~ 改良になってなかった。Python版と同じに戻しました。
~~[Javascript: スプレッド構文とジェネレーターを使ってtransducerっぽいことをする](https://qiita.com/ttatsf/items/4be8a7360dd6bd65fb75) ジェネレーター関連のこと。~~ 本題からずれて無駄に難しくなるので、関数合成関連のコードは削除しました。

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

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

```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: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の次の素数を求めてみました。

```js:JavaScript
{
	const primesGen = primes(); 
  	let x; 
  	while( (x = primesGen.next().value)<=2207); 
  	console.log(x); 
}
=>2209	// = 47*47 正しくない
```
理由は、gcdを計算するための m が 素数を順にかけていく内にどんどん大きくなって[Number.MAX_SAFE_INTEGER](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/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](https://qiita.com/ttatsf/items/4dd12191c60acd61e600#_reference-a3659184688593b8fa20)