JavaScript判断数字是否为质数的方法汇总

判断数字是否为质数是一个常见的算法问题，针对这一问题，我们可以有多种方法来解决。

什么是质数

所谓质数，就是只能被 1 和自身整除的正整数。例如：2、3、5、7、11、13、17、19、23、29、31、37等等。

方法一：暴力枚举法

暴力枚举法，即从2开始，依次枚举到 Math.sqrt(n) 就能判断出一个数是否是质数。

function isPrime(num) {
  if(num <= 1) return false; // 1不是质数
  for(let i = 2; i <= Math.sqrt(num); i++) {
    if(num % i == 0) return false;
  }
  return true;
}

console.log(isPrime(17)) // true
console.log(isPrime(27)) // false

上面的代码中，我们先判定num是否小于等于1，如果是，直接返回false（1不是质数）。然后使用循环从2开始，到 Math.sqrt(num)结束，如果在循环中发现某个数字能够整除num，就说明num不是质数，直接返回false。如果一直到循环结束也没有返回false，则说明num是质数。

方法二：埃氏筛法

埃氏筛法，又叫做厄拉多塞筛法，是一种筛选素数的方法。该方法的基本思路是：先确定需要求出质数的范围 n，然后申请一个长度为 n+1 的布尔类型数组，数组值全部初始化为 true，表示所有数字都是质数。然后从 2 开始枚举，若当前数字为素数，则从它的平方开始，将后续所有该数的倍数都标记为非素数。

function getPrime(n) {
  let arr = []
  for(let i = 0; i <= n; i++) {
    arr[i] = true
  }
  for(let i = 2; i * i <= n; i++) {
    if(arr[i]) {
      for(let j = i * i; j <= n; j += i) {
        arr[j] = false
      }
    }
  }
  let res = []
  for(let i = 2; i <= n; i++) {
    if(arr[i]) {
      res.push(i)
    }
  }
  return res
}

console.log(getPrime(20)) // [2, 3, 5, 7, 11, 13, 17, 19]

上面的代码中，我们首先创建一个长度为n+1的数组arr，数组中的值全部设为true，表示所有数字都是质数。然后从2开始枚举，若当前数字为素数，则从它的平方开始，将后续所有该数的倍数都标记为非素数。最后，再遍历一遍数组arr，如果arr[i]为true，表示i是一个质数，就将其加入到结果数组中。

总结

以上，就是JavaScript判断数字是否为质数的两种方法，暴力枚举法和埃氏筛法。其中，暴力枚举法简单易懂，容易实现，但效率不高，适用于小规模数据的处理。而埃氏筛法虽然稍微有些复杂，但其时间复杂度为O(nloglogn)，效率比较高，适用于大规模数据的处理。

希望通过本文的介绍，您对判断数字是否为质数的方法有了更加深入的了解。