试除法：判断质数

试除法判断一个数是不是质数，并用奇数筛优化性能。

什么是质数

质数就是只能被1和它本身整除的数

• 质数除2外，都是奇数
• 换言之，偶数除2外，都是合数

判断一个数是不是质数

试除法

因式分解任意数n：

• 2： 1 x 2 2 x 1
• 3: 1 x 3 3 x 1
• 4: 1 x 4 2 x 2 4 x 1
• 5: 1 x 5 5 x 1
• 6: 1 x 6 2 x 3 3 x 2 6 x 1 ...

根据乘法交换律，乘数> n 的开方 后面的乘式与前面相同

代码

const isPrime = n => {
    if (n < 2) return false // 1 不是质数，也不是合数
    if (n === 2) return true // 2 是质数
    if (n % 2 === 0) return false // 偶数除 2 外，都是合数
    for (let i = 2; i * i <= n; i++) { // 或写作：i <= Math.sqrt(n)
      if (n % i === 0) return false
    }
    return true
}

例题

762. 二进制表示中质数个计算置位

给你两个整数 left 和 right ，在闭区间 [left, right] 范围内，统计并返回 计算置位位数为质数 的整数个数。 计算置位位数 就是二进制表示中 1 的个数。 例如， 21 的二进制表示 10101 有 3 个计算置位。

答案

var countPrimeSetBits = function(left, right) {
  const isPrime = n => {
    if (n < 2) return false
    if (n === 2) return true
    if (n % 2 === 0) return false
    for (let i = 2; i * i <= n; i++) {
      if (n % i === 0) return false
    }
    return true
  }
  let ans = 0
  for (let i = left; i <= right; i++) {
    let n = i, r = 0
    while (n) {
      n &= n - 1
      r++
    }
    if (isPrime(r)) ans++
  }
  return ans
};

204. 计数质数

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

答案

枚举奇数

解法有很多种，这里用枚举奇数来做，会超时

var countPrimes = function(n) {
  if (n <= 2) return 0
  let ans = 1
  for (let i = 3; i < n; i += 2) {
    if (isPrime(i)) ans++
  }
  return ans
};
const isPrime = n => {
  for (let i = 2; i * i <= n; i++) {
    if (n % i === 0) return false
  }
  return true
}

奇数筛

根据算数基本定理，用已知质数的乘积标记合数，没有被标记的就是质数

分解的存在性：任何大于 1 的自然数，要么本身是质数，要么可以写成 2 个或以上质数的乘积
分解的唯一性：质因子按大小排列，仅有一种方式

var countPrimes = function(n) {
 if (n <= 2) return 0
 const isCom = new Uint8Array(n)
 let ans = 1
 for (let i = 3; i < n; i += 2) {
   if (isCom[i] === 0) {
     for (let j = i; i * j < n; j += 2) isCom[i * j] = 1
     ans++
   }
 } 
 return ans
};