Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

JavaScriptで素数 2

More than 1 year has passed since last update.

参照記事:
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時と全然違うものを返すのでちょっと変な感じ。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away