参照記事：
99 Haskell Problems より、[31] でもその前に
Haskellで素数 2 自分でもやってみた。
Pythonで素数 2 Pythonでやってみた。
JavaScriptで素数 あんまり芳しくなかった前回。
前記事のまとめとこの記事の目的
Haskell界隈の方法をまねしてやってみたら、効率はよさげだったが、2207までしか求められなかった。
この記事では、もっと大きい素数まで効率よく求められるようにします。
JavaScriptでまねしたHaskell界隈のやりかた
をざっくり説明すると、
- ある素数pとその次の素数qと
- p以下の2、3以外の素数をすべて掛けた数mを使って
- pp から qq-2 までの 2、3の倍数を除いた素数の候補から
- mとの最大公約数が1になる数を素数とする
という処理を繰り返し行なっています。
この m が意外とはやくMAX_SAFE_INTEGER に達してしまって、以降、正確に計算できなくなってしまいました。
ちょっと工夫してみた。
変更点 1
m を 単一の整数値でなく、MAX_SAFE_INTEGER 以下の数で因数分解した配列にする。
そうすればMAX_SAFE_INTEGERを超える数も正しく計算できるし、素数の判定も m の全ての要素について最大公約数が1になるか、で簡単に判定することができます。
変更点 2
一回目のzonedPrimesで 7 から 23 までの素数がわかりますが、次の回を 55 = 25 から 77ー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時と全然違うものを返すのでちょっと変な感じ。