js 实现现实素数

实现素数判断与生成

素数判断函数

通过遍历2到该数的平方根之间的所有整数，检查是否能整除目标数。若能整除则非素数。

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 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;
  }, []);
}

性能优化技巧

对于大数判断可采用Miller-Rabin概率测试算法。该方法通过多次随机测试提高准确性。

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(d, n)) return false;
  }
  return true;
}

function millerTest(d, n) {
  let a = 2 + Math.floor(Math.random() * (n - 4));
  let x = modExp(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 modExp(a, b, mod) {
  let result = 1n;
  a = BigInt(a) % BigInt(mod);
  b = BigInt(b);
  mod = BigInt(mod);

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