js判断一个数是不是质数 提供十种方法

以下是10种JS判断一个数是否为质数的方法：

方法1：暴力枚举

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

方法2：优化暴力枚举

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

方法3：6k±1优化

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

方法4：埃氏筛法

function getPrimes(n) {
  const primes = new Array(n + 1).fill(true);
  primes[0] = false;
  primes[1] = false;
  for (let i = 2; i * i <= n; i++) {
    if (primes[i]) {
      for (let j = i * i; j <= n; j += i) {
        primes[j] = false;
      }
    }
  }
  return primes;
}

function isPrime(n) {
  if (n <= 1) {
    return false;
  }
  const primes = getPrimes(n);
  return primes[n];
}

方法5：线性筛法

function getPrimes(n) {
  const primes = [];
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = false;
  isPrime[1] = false;
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) {
      primes.push(i);
    }
    for (let j = 0; j < primes.length && i * primes[j] <= n; j++) {
      isPrime[i * primes[j]] = false;
      if (i % primes[j] === 0) {
        break;
      }
    }
  }
  return primes;
}

function isPrime(n) {
  if (n <= 1) {
    return false;
  }
  const primes = getPrimes(n);
  return primes.includes(n);
}

方法6：费马小定理

function powMod(a, b, p) {
  let res = 1;
  while (b > 0) {
    if (b & 1) {
      res = (res * a) % p;
    }
    a = (a * a) % p;
    b >>= 1;
  }
  return res;
}

function isPrime(n) {
  if (n <= 1) {
    return false;
  }
  if (n <= 3) {
    return true;
  }
  const k = 5;
  for (let i = 0; i < k; i++) {
    const a = Math.floor(Math.random() * (n - 3) + 2);
    if (powMod(a, n - 1, n) !== 1) {
      return false;
    }
  }
  return true;
}

方法7：米勒-拉宾素性检验

function powMod(a, b, p) {
  let res = 1;
  while (b > 0) {
    if (b & 1) {
      res = (res * a) % p;
    }
    a = (a * a) % p;
    b >>= 1;
  }
  return res;
}

function isPrime(n) {
  if (n <= 1) {
    return false;
  }
  if (n <= 3) {
    return true;
  }
  const k = 10;
  let d = n - 1;
  while (d % 2 === 0) {
    d /= 2;
  }
  for (let i = 0; i < k; i++) {
    const a = Math.floor(Math.random() * (n - 3) + 2);
    let x = powMod(a, d, n);
    if (x === 1 || x === n - 1) {
      continue;
    }
    let flag = false;
    while (d !== n - 1) {
      x = (x * x) % n;
      d *= 2;
      if (x === 1) {
        return false;
      }
      if (x === n - 1) {
        flag = true;
        break;
      }
    }
    if (!flag) {
      return false;
    }
  }
  return true;
}

方法8：埃及分数求解

function gcd(a, b) {
  return b === 0 ? a : gcd(b, a % b);
}

function isPrime(n) {
  if (n <= 1) {
    return false;
  }
  if (n === 2 || n === 3) {
    return true;
  }
  let sum = 0;
  for (let i = 2; i < n; i++) {
    if (gcd(i, n) === 1) {
      sum += 1 / i;
    }
  }
  return sum + 1 === n;
}

方法9：质因数分解

function isPrime(n) {
  if (n <= 1) {
    return false;
  }
  let cnt = 0;
  for (let i = 2; i <= n; i++) {
    while (n % i === 0) {
      n /= i;
      cnt += 1;
    }
  }
  return cnt === 1;
}

方法10：Lucas素性检验

function powMod(a, b, p) {
  let res = 1;
  while (b > 0) {
    if (b & 1) {
      res = (res * a) % p;
    }
    a = (a * a) % p;
    b >>= 1;
  }
  return res;
}

function lucasTest(n, p) {
  if (n === 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  const q = Math.floor(n / p);
  const r = n % p;
  return powMod(lucasTest(q, p), 2, p) * powMod(2, r, p) % p;
}

function isPrime(n) {
  if (n <= 1) {
    return false;
  }
  if (n === 2 || n === 3) {
    return true;
  }
  const primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
  for (const p of primes) {
    if (n === p) {
      return true;
    }
    if (n % p === 0) {
      return false;
    }
    if (lucasTest(n, p) !== 1) {
      return false;
    }
  }
  return true;
}