质数js实现

质数判断的 JavaScript 实现

质数是指大于1的自然数，且只能被1和它本身整除的数。以下是几种常见的质数判断方法及对应的 JavaScript 实现。

基础判断方法

通过遍历2到n-1之间的所有数，判断是否能整除n。

function isPrime(n) {
  if (n <= 1) return false;
  for (let i = 2; i < n; i++) {
    if (n % i === 0) return false;
  }
  return true;
}

优化方法：减少遍历范围

只需遍历2到√n之间的数，因为如果n有大于√n的因数，必然对应一个小于√n的因数。

function isPrimeOptimized(n) {
  if (n <= 1) return false;
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) return false;
  }
  return true;
}

进一步优化：跳过偶数

除2外，所有偶数都不是质数，可以跳过偶数判断。

function isPrimeFurtherOptimized(n) {
  if (n <= 1) return false;
  if (n === 2) return true;
  if (n % 2 === 0) return false;
  for (let i = 3; i <= Math.sqrt(n); i += 2) {
    if (n % i === 0) return false;
  }
  return true;
}

生成质数列表

生成从2到n的所有质数列表，可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）。

function sieveOfEratosthenes(n) {
  const primes = new Array(n + 1).fill(true);
  primes[0] = primes[1] = false;
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (primes[i]) {
      for (let j = i * i; j <= n; j += i) {
        primes[j] = false;
      }
    }
  }
  return primes
    .map((isPrime, index) => (isPrime ? index : null))
    .filter((num) => num !== null);
}

实际应用示例

console.log(isPrime(7)); // true
console.log(isPrimeOptimized(9)); // false
console.log(isPrimeFurtherOptimized(2)); // true
console.log(sieveOfEratosthenes(20)); // [2, 3, 5, 7, 11, 13, 17, 19]

这些方法可以根据实际需求选择使用，基础方法适用于简单场景，优化方法更适合性能敏感的应用。