如何在 JavaScript 中高效检查素数？

如何在 JavaScript 中确定素数

在 JavaScript 中，识别素数是一项常见的编程任务。素数是大于 1 的正整数，除了 1 和它本身之外，不能被任何其他正整数整除。

解决方案 1：朴素方法

提供的代码代码片段提供了一种检查数字是否为素数的简单方法：

<code class="js">let inputValue = 7;
let isPrime = inputValue == 1 ? false : true;

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：高效方法

检查素数的改进方法是：

<code class="js">const isPrime = num => {
  for (let i = 2, s = Math.sqrt(num); i <= s; i++) {
    if (num % i === 0) return false;
  }
  return num > 1;
};</code>

这段代码利用这样一个事实：如果一个数不是质数，则它的因数小于或等于其平方根。通过检查平方根以下的因子，我们可以有效地消除潜在因子。

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

空间复杂度：O(1)

以上是如何在 JavaScript 中高效检查素数？的详细内容。更多信息请关注PHP中文网其他相关文章！