如何在 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中文網其他相關文章！