JavaScriptで素数を求めるなどやった - 雑記

以前、と言っても相当前のことだけれど、会社をやっている友達と飲んでいて、そこの強いエンジニアの人も来ていた。その人はプログラミングを教えるということも行なっており、生徒に出した問題についての話になった。
それが、ある数までの素数を求める、というようなものだった。
調べることは許可されており、確か100までの全ての素数を吐き出すようなプログラムを書け、というような話だったと思う。
僕は素数ってどうやって求めるんやろ、と思いながらも相槌を打っていた。
簡単そうでもあるけど、難しそうでもある。

それからしばらく全く忘却していたが、昨日、全く退屈で終わらないような作業をしている時に、ふとその事を思い出してしまった。

全く脳の使わない仕事をしばらくしている反動か知らないけれど、どうにもやりたくなってしまったのでやってみた。

素数

素数とは、その数と1以外では割り切ることのできない数のことで、それは学校で習った気がする。というか、こいつ公式ないのか？という気持ちになって調べてみたらなかった。

というわけで力技で考えるのならば、与えられた数までの全ての数をその数までの全ての数字で割ってみて、1つも割り切れなければ素数だという事を繰り返せば求めることができそうだ。

その場合だけど、5までの素数を求めるとして

5 / 4, 5 / 3, 5 / 2, 4 / 3, 4 / 2, 3 / 2

という形になる。
まぁ、5位なら求められそうなもんだけど、10000とかだと計算量が増えて、たちまちブラウザがフリーズしそうな気持ちがしてくる。

そういうわけでこんな非効率なことはやっとれんな、と思ったところで、良さそうなものを発見した。

エラトステネスの篩（ふるい）

これが何かと言うと、Wikipedia先生に聞いてみるとなんとなくわかる。

https://ja.m.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9

わかるとか言ったけど、僕はすぐには分からなかった。なんとなく読んで、へーっとなって、寝て起きるとようやく理解できてきたというのが本当のところだった。

これはつまり、以下の手順で求めることができそうなことがわかった。

ある数(max)の平方根を求める(maxDevide)
maxDevideまでの素数を全て求める(primesForDevide)
maxDevideより大きい、maxまでの全ての整数をprimesForDevideで割り、1度も割り切れなかったものと、primesForDevideを合成する

そういうわけでやってみた。

実装💪

const getPrimes = max => {
  if (max < 2) {
    return [];
  }
  const getMaxDevide = n => Math.floor(Math.sqrt(n));
  const maxDevide = getMaxDevide(max);
  const getPrimesByMaxDevide = (num, primesArray = []) => {
    if (num <= 2) {
      return [2, ...primesArray];
    }

    const isPrime = ![...Array(getMaxDevide(num) + 1).keys()]
      .filter(n => n > 1)
      .some(n => num % n === 0);

    return getPrimesByMaxDevide(
      num - 1,
      isPrime ? [num, ...primesArray] : primesArray
    );
  };

  const devidePrimes = getPrimesByMaxDevide(maxDevide);

  return [
    ...devidePrimes,
    ...[...Array(max + 1).keys()].filter(
      n => n > maxDevide && !devidePrimes.some(d => n % d === 0)
    )
  ];
};

こんな感じでうまいこといけてるみたい。 1,000,000くらいの数与えてもいけるみたいなので、パフォーマンス的にも問題なさそう。

だけどダラッとかかれているので読みにくすぎるのでリファクタする。

const getMaxDevide = n => Math.floor(Math.sqrt(n));

const isPrime = num =>
  ![...Array(getMaxDevide(num) + 1).keys()]
    .filter(n => n > 1)
    .some(n => num % n === 0);

const getPrimesByCheckingAllNumbers = (num, primesArray = []) =>
  num <= 2
    ? [2, ...primesArray]
    : getPrimesByCheckingAllNumbers(
        num - 1,
        isPrime(num) ? [num, ...primesArray] : primesArray
      );

const getPrimes = max => {
  if (max < 2) {
    return [];
  }
  const maxDevide = getMaxDevide(max);
  const devidePrimes = getPrimesByCheckingAllNumbers(maxDevide);

  return [
    ...devidePrimes,
    ...[...Array(max + 1).keys()].filter(
      n => n > maxDevide && !devidePrimes.some(d => n % d === 0)
    )
  ];
};

マシになりましたか？

所感

なんというか、素数を調べるところからやっても2時間くらいかかりそう。
コード書くだけでも割とかかった。
これが入社試験とかで、素数を調べるところからだったら死んでたな。