JavaScript 中的 isPrime

1. 在 JavaScript 中檢查數字是否為素數的簡單解決方案
2. 在 JavaScript 中檢查數字是否為素數的平方根解決方案

素數大於一，有兩個因數—1 和它自己。這意味著質數在除以其他數字時總是留下餘數。其他大於 1 且有兩個以上因數的數稱為合數。

本文將討論在 JavaScript 中檢查數字是否為素數的不同方法。

在 JavaScript 中檢查數字是否為素數的簡單解決方案

檢查一個數 n 是否為素數的最簡單方法是從 2 迭代到 n-1，然後檢查 n 是否可被它們中的每一個整除。

function isPrime(n) {
  if (n <= 1) return false;
  for (var i = 2; i <= n - 1; i++)
    if (n % i == 0) return false;
  return true;
}

console.log(isPrime(70));
console.log(isPrime(23));

時間複雜度

我們從 2 到 n-1 迭代 n-2 次。該解決方案的時間複雜度為 O(n)。

空間複雜度

該解決方案的空間複雜度為 O(1)。

在 JavaScript 中檢查數字是否為素數的平方根解決方案

上面的解決方案可以通過迭代直到 sqrt(n) 來改進。它基於 sqrt(n) * sqrt(n) = n 這一事實，並且必須至少有一個因子小於等於 sqrt(n)。如果我們在 [2, sqrt(n)] 的範圍內找不到任何因子，則表示數 n 是質數。

function isPrime(n) {
  if (n <= 1) return false;
  for (var i = 2; i <= Math.sqrt(n); i++)
    if (n % i == 0) return false;
  return true;
}

console.log(isPrime(70));
console.log(isPrime(23));

時間複雜度

由於我們迭代了第一個 sqrt(n) 潛在因素，因此上述解決方案的時間複雜度為 sqrt(n)。

空間複雜度

該解決方案的空間複雜度為 O(1)。