JavaScript 中的 isPrime
Harshit Jindal
2023年1月30日
2022年5月5日
素數大於一,有兩個因數—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)
。
Author: Harshit Jindal
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn