JavaScriptで素数を判定する方法

1. 方法1: 単純な方法 この方法では、2からその数の平方根までの数で割り切れるかどうかを調べます。

function isPrime(num) {
  if (num <= 1) {
    return false;
  }
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) {
      return false;
    }
  }
  return true;
}

2. 方法2: エラトステネスの篩 エラトステネスの篩は、ある数の範囲内の素数を見つける効率的なアルゴリズムです。

function sieveOfEratosthenes(num) {
  const primes = [];
  const isPrime = new Array(num + 1).fill(true);
  isPrime[0] = false;
  isPrime[1] = false;
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= num; j += i) {
        isPrime[j] = false;
      }
    }
  }
  for (let i = 2; i <= num; i++) {
    if (isPrime[i]) {
      primes.push(i);
    }
  }
  return primes;
}

3. 方法3: ミラーラビン素数判定法 ミラーラビン素数判定法は、確率的な方法ですが、高速に素数を判定することができます。

function isPrimeMillerRabin(num, k) {
  if (num <= 1) {
    return false;
  }

  if (num === 2 || num === 3) {
    return true;
  }
  if (num % 2 === 0) {
    return false;
  }
  const { s, r } = decompose(num - 1);
  for (let i = 0; i < k; i++) {
    const a = getRandomInt(2, num - 2);
    let x = modPow(a, r, num);
    if (x === 1 || x === num - 1) {
      continue;
    }
    let j = 1;
    while (j < s && x !== num - 1) {
      x = modPow(x, 2, num);
      if (x === 1) {
        return false;
      }
      j++;
    }
    if (x !== num - 1) {
      return false;
    }
  }
  return true;
}
function decompose(num) {
  let s = 0;
  let r = num;
  while (r % 2 === 0) {
    r /= 2;
    s++;
  }
  return { s, r };
}
function getRandomInt(min, max) {
  min = Math.ceil(min);
  max = Math.floor(max);
  return Math.floor(Math.random() * (max - min + 1)) + min;
}
function modPow(base, exponent, modulus) {
  if (modulus === 1) {
    return 0;
  }
  let result = 1;
  base = base % modulus;
  while (exponent > 0) {
    if (exponent % 2 === 1) {
      result = (result * base) % modulus;
    }
    exponent = exponent >> 1;
    base = (base * base) % modulus;
  }

  return result;
}

これらの方法を使って素数を判定することができます。素数判定のアルゴリズムの選択は、入力の範囲やパフォーマンス要件に応じて行う必要があります。