如何在 JavaScript 中高效判断一个数字是否为质数？

JavaScript 中的素数检查

本文解决了使用 JavaScript 确定给定数字是否为素数的问题。素数是大于 1 的整数，除了 1 和它本身之外，不能被任何其他自然数整除。

解决方案 1

传统方法是从 2 开始迭代输入数字的平方根，并检查该数字是否可以被其中任何一个整除。如果是，则不是素数；

<code class="javascript">let inputValue = 7;
let isPrime = inputValue == 1 ? false : true; // because 1 is not prime

for (let i = 2; i < inputValue; i++) {
  inputValue % i == 0 ? (isPrime *= false) : (isPrime *= true);
}

alert(`${inputValue} is ${isPrime ? 'prime' : 'not prime'} number`);

时间复杂度：O(sqrt(n))
空间复杂度：O(1)

解决方案 2

另一种方法利用了大于 2 的素数不能是奇数这一事实。因此，只需检查能否被 2 整除，然后检查奇数直至输入数的平方根就足够了。此优化显着减少了执行时间。

<code class="javascript">const isPrime = num => {
  if (num <= 1) return false;
  if (num <= 3) return true;
  if (num % 2 == 0 || num % 3 == 0) return false;
  for (let i = 5; i * i <= num; i += 6) {
    if (num % i == 0 || num % (i + 2) == 0) return false;
  }
  return true;
};</code>

时间复杂度：O(sqrt(n))
空间复杂度：O(1)

以上是如何在 JavaScript 中高效判断一个数字是否为质数？的详细内容。更多信息请关注PHP中文网其他相关文章！