JavaScript 中的 isPrime

Harshit Jindal 2023年10月12日
  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
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