质数是指只能被1和自身整除的正整数，是数学中的重要概念，在计算机科学中也有着广泛的应用。在javascript中，我们可以使用以下几种方法来计算质数。
- 暴力枚举法
暴力枚举法是一种简单直接的计算质数的方法。我们可以从2开始遍历到n-1，依次判断每个整数是否能够整除n。如果存在一个整数m能够整除n，则n不是质数。如果对于每个整数m都不能整除n，则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;
}- Sieve of Eratosthenes
Sieve of Eratosthenes是一种更快速计算质数的方法。它的基本思想是先把所有正整数按顺序排列，然后从2开始依次筛选出能够整除2的数，然后把能够整除3的数筛选出来，然后把能够整除5的数筛选出来，以此类推，直到不能再筛选出质数为止。
以下是Sieve of Eratosthenes的Javascript实现代码：
立即学习“Java免费学习笔记（深入）”；
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;
}, []);
}- Miller-Rabin算法
Miller-Rabin算法是一种概率性的质数测试算法，它基于一个重要的定理：如果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中计算质数的三种常用方法，不同的应用场景下可以选择适合的方法来计算质数。
