JavaScriptで素数を計算する方法

素数とは、1 とそれ自体でしか割りることができない正の整数を指します。これは数学の重要な概念であり、コンピューター サイエンスで広く使用されています。 Javascript では、次のメソッドを使用して素数を計算できます。

1. 暴力的な列挙法

暴力的な列挙法は、素数を計算する単純かつ直接的な方法です。 2 から開始して n-1 までたどり、各整数が n を割り切れるかどうかを判断できます。 n を割る整数 m がある場合、n は素数ではありません。 n がすべての整数 m で割り切れない場合、n は素数になります。

以下は、暴力的な列挙メソッドの Javascript 実装コードです:

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

2. エラトステネスのふるい

エラトステネスのふるいは計算を高速化する方法です。素数法。その基本的な考え方は、まずすべての正の整数を順番に並べ、次に 2 で割れる数を 2 から順に除外し、次に 3 で割ることができる数を除外し、次に割ることができる数を除外することです。 5 ずつ、というように、素数がフィルターで除外できなくなるまで続けます。

以下はエラトステネスの篩の Javascript 実装コードです:

function sieveOfEratosthenes(n) {
  const primes = new Array(n + 1).fill(true);

  primes[0] = false;
  primes[1] = false;

  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (primes[i]) {
      for (let j = i * i; j <= n; j += i) {
        primes[j] = false;
      }
    }
  }

  return primes.reduce((acc, cur, index) => {
    if (cur) {
      acc.push(index);
    }

    return acc;
  }, []);
}

3. ミラーラビン アルゴリズム

ミラーラビン アルゴリズムは確率的素数です。重要な定理に基づいたテスト アルゴリズム: n が合成数の場合、n より小さい正の整数 a の少なくとも半分は a^(n-1) mod n != 1 を満たす。 Miller-Rabin アルゴリズムの核心は、指定された整数 n に対して k 個のランダム テストを実行し、これを使用して n が素数かどうかを判断することです。通常、より正確な結果を得るために必要なテストは 15 ～ 20 回だけです。

次は、Miller-Rabin アルゴリズムの Javascript 実装コードです:

// 快速幂算法
function powerMod(a, b, m) {
  let res = 1;

  while (b) {
    if (b & 1) {
      res = (res * a) % m;
    }

    a = (a * a) % m;
    b >>= 1;
  }

  return res;
}

function isPrime(num, k) {
  if (num < 2) {
    return false;
  }

  if (num === 2 || num === 3) {
    return true;
  }

  let d = num - 1;
  let r = 0;

  while (d % 2 === 0) {
    d /= 2;
    r++;
  }

  for (let i = 0; i < k; i++) {
    const a = 2 + Math.floor(Math.random() * (num - 3));
    let x = powerMod(a, d, num);

    if (x === 1 || x === num - 1) {
      continue;
    }

    let flag = false;

    for (let j = 1; j < r; j++) {
      x = (x * x) % num;

      if (x === num - 1) {
        flag = true;
        break;
      }
    }

    if (!flag) {
      return false;
    }
  }

  return true;
}

上記は、JavaScript で素数を計算するための 3 つの一般的な方法です。素数を計算する適切な方法を選択できます。さまざまなアプリケーションシナリオでの数値。

以上がJavaScriptで素数を計算する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。