JavaScript 中的 isPrime

Harshit Jindal 2023年1月30日 2022年5月5日
  1. 在 JavaScript 中檢查數字是否為素數的簡單解決方案
  2. 在 JavaScript 中檢查數字是否為素數的平方根解決方案
JavaScript 中的 isPrime

素數大於一,有兩個因數—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)

Harshit Jindal avatar Harshit Jindal avatar

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