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