javascript怎么计算质数-前端问答-PHP中文网

javascript怎么计算质数

王林

发布： 2023-05-09 12:23:36

原创

1052人浏览过

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

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