javascript怎么计算质数

时间：2023-05-10 02:16

质数是指只能被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实现代码：

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中计算质数的三种常用方法，不同的应用场景下可以选择适合的方法来计算质数。

以上就是javascript怎么计算质数的详细内容，更多请关注Gxl网其它相关文章！