JavaScriptで素数を計算する方法-フロントエンドQ&A-php.cn

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

暴力的な列挙法

暴力的な列挙法は、素数を計算する単純かつ直接的な方法です。 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 から順に除外し、次に 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; }, []); }

ログイン後にコピー

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

ミラーラビンアルゴリズムは確率的素数です。重要な定理に基づいたテストアルゴリズム: 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 サイトの他の関連記事を参照してください。