JavaScriptで素数を扱う

備忘録。
素数列挙と素数判定はこちらを参考にしました。
もっと速いのがあればご教示ください。

素数列挙

const getPrimes = n => {
  if (n < 2) return [];
  const primes = range(n);
  primes[1] = 0;
  const limit = Math.sqrt(n);
  for (let prime of primes) {
    if (prime > limit) break;
    if (prime === 0) continue;
    for (let non_prime of range(2*prime, n, prime)) primes[non_prime] = 0;
  }
  return primes.filter(p => p !== 0);
};

※range関数はこちらを参考に。
エラトステネスのふるいというアルゴリズムを使います。これは小中学校の算数数学の教科書にも載っていた記憶があります。

素数判定

const isPrime = n => {
  if (n < 2) return false;
  if (n === 2 || n === 3 || n === 5) return true;
  if (n % 2 === 0 || n % 3 === 0 || n % 5 === 0) return false;
  let prime = 7;
  let step = 4;
  const limit = Math.sqrt(n);
  while (prime <= limit) {
    if (n % prime === 0) return false;
    prime += step;
    step = 6 - step;
  }
  return true;
};

5以上の素数は6で割った余りが±1という性質があるので、これを使って割る回数を減らしています。

素因数分解

const getPrimeFactors = n => {
  if (n < 2) return [];
  if (n === 2 || n === 3 || n === 5) return [n];
  if (n % 2 === 0) return [2, ...getPrimeFactors(n/2)];
  if (n % 3 === 0) return [3, ...getPrimeFactors(n/3)];
  if (n % 5 === 0) return [5, ...getPrimeFactors(n/5)];
  let prime = 7;
  let step = 4;
  const limit = Math.sqrt(n);
  while (prime <= limit) {
    if (n % prime === 0) return [prime, ...getPrimeFactors(n/prime)];
    prime += step;
    step = 6 - step;
  }
  return [n];
};

スプレッド演算子は便利！みんなも使おう！！