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
3
Help us understand the problem. What is going on with this article?
@ttatsf

JavaScriptで素数

More than 1 year has passed since last update.

参照記事:
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

3
Help us understand the problem. What is going on with this article?
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

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
3
Help us understand the problem. What is going on with this article?