js实现质数

判断质数的基本方法

质数是大于1的自然数，除了1和它本身外没有其他约数。在JavaScript中可以通过循环和条件判断实现质数检测。

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

优化算法效率

基础方法存在效率问题，可以通过数学优化减少循环次数。只需要检查到√n即可，因为大于√n的因数必然对应一个小于√n的因数。

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

生成质数列表

埃拉托斯特尼筛法能高效生成指定范围内的所有质数。其原理是逐步筛除非质数的倍数。

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

  for (let i = 2; i <= Math.sqrt(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;
  }, []);
}

处理大数的情况

对于非常大的数字，可以考虑使用概率性测试算法如Miller-Rabin测试，虽然不能100%准确但效率更高。

function isProbablyPrime(n, k = 5) {
  if (n <= 1) return false;
  if (n <= 3) return true;

  let d = n - 1;
  while (d % 2 === 0) d /= 2;

  for (let i = 0; i < k; i++) {
    if (!millerTest(n, d)) return false;
  }
  return true;
}

function millerTest(n, d) {
  let a = 2 + Math.floor(Math.random() * (n - 4));
  let x = modPow(a, d, n);

  if (x === 1 || x === n - 1) return true;

  while (d !== n - 1) {
    x = (x * x) % n;
    d *= 2;
    if (x === 1) return false;
    if (x === n - 1) return true;
  }
  return false;
}

function modPow(a, b, mod) {
  let result = 1n;
  a = BigInt(a);
  b = BigInt(b);
  mod = BigInt(mod);

  a = a % mod;
  while (b > 0n) {
    if (b % 2n === 1n) result = (result * a) % mod;
    a = (a * a) % mod;
    b = b / 2n;
  }
  return Number(result);
}