js 实现现实素数

判断素数的方法

素数是大于1的自然数，除了1和它本身外没有其他约数。在JavaScript中可以通过以下方法判断一个数是否为素数：

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;
}

生成素数列表

要生成一定范围内的素数列表，可以结合上述判断方法：

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

优化算法

埃拉托斯特尼筛法是一种更高效的素数生成算法：

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

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

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

性能比较

对于小范围数字（如<1000），简单判断法足够高效。对于大范围数字（如>10000），筛法性能优势明显。测试10万以内的素数：

console.time('Simple check');
generatePrimes(100000);
console.timeEnd('Simple check');

console.time('Sieve');
sieveOfEratosthenes(100000);
console.timeEnd('Sieve');