当前位置：首页 > JavaScript

js实现质数

2026-04-06 03:58:27JavaScript

判断一个数是否为质数

质数是指大于1的自然数，除了1和它本身外没有其他约数。以下是一个判断质数的JavaScript函数：

js实现质数

function isPrime(num) {
  if (num <= 1) return false;
  if (num <= 3) return true;

  if (num % 2 === 0 || num % 3 === 0) return false;

  for (let i = 5; i * i <= num; i += 6) {
    if (num % i === 0 || num % (i + 2) === 0) {
      return false;
    }
  }
  return true;
}

生成指定范围内的质数列表

以下函数可以生成从2到指定上限的所有质数：

js实现质数

function generatePrimesUpTo(max) {
  const primes = [];
  for (let i = 2; i <= max; i++) {
    if (isPrime(i)) {
      primes.push(i);
    }
  }
  return primes;
}

使用埃拉托斯特尼筛法优化

对于大量质数判断，埃拉托斯特尼筛法更高效：

function sieveOfEratosthenes(limit) {
  const sieve = new Array(limit + 1).fill(true);
  sieve[0] = sieve[1] = false;

  for (let i = 2; i * i <= limit; i++) {
    if (sieve[i]) {
      for (let j = i * i; j <= limit; j += i) {
        sieve[j] = false;
      }
    }
  }

  return sieve.reduce((primes, isPrime, num) => {
    if (isPrime) primes.push(num);
    return primes;
  }, []);
}

性能优化建议

对于大数判断，可以进一步优化：

只检查到平方根的整数部分
跳过偶数检查（除了2）
使用6k±1的形式进行迭代检查

使用示例

console.log(isPrime(17)); // true
console.log(generatePrimesUpTo(30)); // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
console.log(sieveOfEratosthenes(100).length); // 25个质数

这些方法提供了从简单判断到高效生成质数的不同实现方式，可根据具体需求选择合适的方法。