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)。