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(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, index) => {
    if (isPrime) primes.push(index);
    return primes;
  }, []);
}

优化判断方法

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

function isPrimeOptimized(n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 === 0 || n % 3 === 0) return false;

  const sqrtN = Math.sqrt(n);
  for (let i = 5; i <= sqrtN; i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) {
      return false;
    }
  }
  return true;
}

性能比较

对于不同规模的素数判断，各种方法性能表现不同：

• 简单试除法适合小数字
• 筛法适合批量生成素数
• 优化后的方法适合大数判断

实际应用中应根据具体需求选择合适的方法。