素数を求めるコード

私はちょっと試しにプログラムを書いてみるときに、素数を求めるコードを書いたりします。

素数を求めるコード

ということで、素数を求めるコードをいくつかご紹介します。
言語は何でも良いのだけど、今回はJavaScriptのジェネレータ関数で。
JavaScriptのジェネレータ関数については、以下を参照ください。

function* 宣言 - JavaScript | MDN

まず思いつくコード

素数を求めるコードと言って思いつくのは以下のようなコードだと思います。

function* prime1() {
  yield 2n;
  for (let cand = 3n; ; cand += 2n) {
    let ok = true;
    for (let test = 3n; test * test <= cand; test += 2n) {
      if (cand % test == 0n) {
        ok = false;
        break;
      }
    }
    if (ok) {
      yield cand;
    }
  }
}

2は先に素数として返しておき、その後は候補となる3以後の奇数(上のコードの場合 cand )に対して、同じく3以後の奇数で順に余りを求めていき、割り切れる(余り=0)ものがない場合、それが素数というもの。
定数の末尾にnがついているのはそれがBigInt型であることを示します。素数は大きな数となってしまうので、BigIntで扱っています、

BigInt - JavaScript | MDN

試す数を $${test \times test \leqq cand}$$ までにしているのはその後の数を試しても無駄だから。ちょっと説明すると、$${cand}$$ が $${x \times y}$$ で表される合成数(素数ではない数)だったとします。$${x}$$ を 3, 5, 7… と変えていくわけですが、最初は$${x \leqq y}$$なのですが、$${x > \sqrt{cand}}$$ から$${x > y}$$となり、$${y}$$ の方が小さくなります。$${x \times y = y \times x}$$であり、$${\sqrt{cand}}$$ より小さい数は既に試されているので、$${x}$$が$${\sqrt{cand}}$$以後の数を試す必要はありません。

見つけた素数を控えておく

「まず思いつくコード」では無条件に3から奇数を使って割り切れるかどうかを試していました。当然その数には合成数も含まれているわけなので無駄があります。
そこで見つけた素数を使って試すようにしたものが以下。

function* prime2() {
  yield 2n;
  const primes = [];
  for (let cand = 3n; ; cand += 2n) {
    let ok = true;
    for (const test of primes) {
      if (test * test > cand) break;
      if (cand % test == 0n) {
        ok = false;
        break;
      }
    }
    if (ok) {
      yield cand;
      primes.push(cand);
    }
  }
}

ここでも $${test \times test \leqq cand}$$ に限定するロジックを入れています。
見つかった素数をすべて配列に入れているので、メモリを消費してしまいます。

逆に合成数を求めておく

ある数が素数かどうか確認するのではなく、次の合成数が何か求めておけば、それに該当しないものが素数ということになります。

function* prime3() {
  yield 2n;
  const m = new Map();
  for (let cand = 3n; ; cand += 2n) {
    if (m.has(cand)) {
      let prime = m.get(cand),
        comp = cand + prime * 2n;
      m.delete(cand);
      while (m.has(comp)) comp += prime * 2n;
      m.set(comp, prime);
    } else {
      yield cand;
      m.set(cand * cand, cand);
    }
  }
}

このアルゴリズムは、以前ネットのどこかで見かけたものを自分なりに修正したものです(すいません、元ネタを示すべきなのでしょうけど、どこだったかは忘れてしまいました)。
合成数をキーとして素数を保持した辞書を用意し、試す数がキーになければ素数、あれば次の合成数を計算し、新たに辞書に追加(以前のものはもう不要なので削除)という処理になっています。
素数の判断が一回で済むのがメリットです。メモリはやはり消費します。

処理時間の違い

3種類ほど素数を求めるコードを紹介しましたが、ではそのアルゴリズムによってどれくらい処理時間に差があるのか、見ていきましょう。
ということで、以下のようなプログラムを書きました。node.jsで動作するプログラムです。

const { performance } = require("perf_hooks");

function* prime1() {
  yield 2n;
  for (let cand = 3n; ; cand += 2n) {
    let ok = true;
    for (let test = 3n; test * test <= cand; test += 2n) {
      if (cand % test == 0n) {
        ok = false;
        break;
      }
    }
    if (ok) {
      yield cand;
    }
  }
}

function* prime2() {
  yield 2n;
  const primes = [];
  for (let cand = 3n; ; cand += 2n) {
    let ok = true;
    for (const test of primes) {
      if (test * test > cand) break;
      if (cand % test == 0n) {
        ok = false;
        break;
      }
    }
    if (ok) {
      yield cand;
      primes.push(cand);
    }
  }
}

function* prime3() {
  yield 2n;
  const m = new Map();
  for (let cand = 3n; ; cand += 2n) {
    if (m.has(cand)) {
      let prime = m.get(cand),
        comp = cand + prime * 2n;
      m.delete(cand);
      while (m.has(comp)) comp += prime * 2n;
      m.set(comp, prime);
    } else {
      yield cand;
      m.set(cand * cand, cand);
    }
  }
}


const N = 200000;
const PRIMES = [prime1, prime2, prime3];

for (let prime of PRIMES) {
  let n = 0,
    p = 0;
  const s = performance.now();
  for (p of prime()) {
    if (++n >= N) break;
  }
  const l = performance.now() - s;
  console.log(prime.name, n, p, l);
}

実行時間は環境によって変わるとは思いますが、私の環境では以下のような結果になりました。

❯ node test.js
prime1 200000 2750159n 40034.435799986124
prime2 200000 2750159n 12824.687000006437
prime3 200000 2750159n 1272.0990000069141

1番目が40秒、2番目が13秒くらい、3番目が2秒未満。圧倒的に3番目のアルゴリズムが速いです。やはり処理時間を決めるのは確認のための計算回数ということになると思います。

さいごに

いかがでしたでしょうか。今回は素数を求めるアルゴリズムについて書きました。
何かの参考になったら幸いです。