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