2021/05/03 - Leetcode#204 计数质数

[lxinr]

题目

统计所有小于非负整数 n 的质数的数量

示例1:

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 

示例2:

输入：n = 0
输出：0

提示：

$0 <= n <= 5 * 10^6$

质数的概念

又称素数，指在大于$1$的自然数中，除了$1$和该数自身外，无法被其他自然数整除的数（也可定义为只有$1$与该数本身两个正因数的数）

一、试除法

思路

将n除以每个大于1且小于等于$\sqrt n$的自然数，只要其中有一个结果为整数，则代表其不是质数

实际上，也不需要所有在范围内的自然数都去除，只有判断不是合数(不是素数的自然数)的数即可，但也并不需要那么麻烦，只需要去判断奇数就可以了，偶数它必然是合数，因为除了2以外，任何一个偶数都至少有2这个约数

function countPrimes(n) {
  if(n <= 2) return 0 
  if( n === 3) return 1

  let num = 0
  // 判断是否为质数
  function isPrime(x) {
    if(x <= 3) return true
    const sqrt = Math.ceil(Math.sqrt(x))
    // 因为我们已经排除了所有的偶数，所以可以直接+2，跳过偶数，来减少循环次数
    for(let i = 3; i <= sqrt; i+=2) {
      // 如果能被整除则代表不是质数
      if (x % i === 0) return false
    }
    return true
  }

  for(let i = 2; i < n; i++) {
    // 任何一个除2以外的偶数都至少有2这个约数，因此不需要去判断
    if (i > 2 && i % 2 === 0) continue
    if(isPrime(i)) num++
  }

  return num
}

但很可惜，该方法超出了时间限制，因为在判断很大的数时，计算量会变得非常大，因此此方法在较大数时不适用

二、埃拉托斯特尼筛法(埃氏筛)

所使用的原理是从2开始，将每个素数的各个倍数，标记成合数。一个素数的各个倍数，是一个差为此素数本身的等差数列。此为这个筛法和试除法不同的关键之处，后者是以素数来测试每个待测数能否被整除。
埃拉托斯特尼筛法是列出所有小素数最有效的方法之一，主要被用来给出$10^7$以下的质数

思路

如果一个数$x$是质数，则大于$x$的$x$的倍数就一定不可能是质数
即可以从$2x$开始处理

实现1：

function countPrimes(n) {
  let count = 0
  const numArr = Array(n).fill(1)
  for(let i = 2; i < n; i++) {
    if(numArr[i]) {
      count++
      // 对所有的倍数数据，标记为0，即表示不可能为质数，直接跳过
      for(let j = i * 2; j < n; j += i) {
        numArr[j] = 0
      }
    }
  }
  return count
}

但其实我们可以看到的是，我们不需要从$2x$开始，因为$2x$、$3x$、$4x$...直到$(x-1)x$都会在$x$之前被遍历到，因此我们直接从$xx$开始即可

改良实现2:

function countPrimes(n) {
  let count = 0
  const numArr = Array(n).fill(1)
  for(let i = 2; i < n; i++) {
    if(numArr[i]) {
      count++
      // 对所有的倍数数据，标记为0，即表示不可能为质数，直接跳过
      // 从i*i开始遍历
      for(let j = i * i; j < n; j += i) {
        numArr[j] = 0
      }
    }
  }
  return count
}

三、Fermat素性检验(费马素性检验)

算法逻辑：

给定奇整数$m≥3$和安全参数$k=5$

1. 随机选取整数$a$,$2≤a≤m-2$
2. 计算$g=(a, m)$，如果$g=1$，转（3）；否则，跳出，$m$为合数
3. 计算$r =a^{m-1}(mod m)$，如果$r=1$,$m$可能是素数，转（1）；否则，跳出，$m$为合数
4. 重复上述过程$k$次，如果每次得到$m$可能为质数，则$m$为质数的概率为$1 - \frac1{2^k}$

function countPrimes(n) {
  if(n <= 2) return 0 
  if( n === 3) return 1

  let num = 0

  // 生成[minN, maxN]内的随机整数
  function randomNum(minN, maxN) {
    return Math.floor(Math.random() * (maxN - minN + 1) + minN)
  }

  // 得到两个数的最大公约数
  function gcd(a, b) {
    if(b === 0) return a
    return gcd(b, a%b)
  }
  
  function isPrime(x, k = 5) {

    for(let i = 0; i < k; i++) {
      const v = randomNum(2, x - 2)
      if(gcd(v, x) !== 1) return false
      // 这里因为数太大，结果会不精确，因此在这里最后应该进行专门的大数比较
      if(Math.pow(v, x - 1) % x !== 1) return false
    }
    return true
  }

  for(let i = 2; i < n; i++) {
    // 任何一个除2以外的偶数都至少有2这个约数，因此不需要去判断
    if (i > 2 && i % 2 === 0) continue
    if(isPrime(i)) num++
  }

  return num

}

注：上述代码因为涉及到大数判断，因此目前结果是不准确的

参考资料

[1] 筛法: https://zh.wikipedia.org/wiki/%E8%B4%A8%E6%95%B0

[2] 费马素性检验: https://zh.wikipedia.org/wiki/%E8%B4%B9%E9%A9%AC%E7%B4%A0%E6%80%A7%E6%A3%80%E9%AA%8C

[3] [Fermat素性检验算法: https://blog.csdn.net/joker_clown/article/details/101054453](