计算素数个数的三段进阶

发表于 | 分类于 | 阅读次数:
字数统计: 1,683 | 阅读时长 ≈ 7

今天坐leetcode上的Count Primes这道题，题目要求比较的简单：Count the number of prime numbers less than a non-negative number, n. 就是给一个数字，然后输出从0到这个数字内有多少个素数。
老办法先实现后优化，实现之后发现优化真不容易，借助外界各种资源后，差不多算是达到了自己想达到的效果，故记录一下此次一波三折的优化。

低阶版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function isPrimes(num) {
  for(var j = 2; j <= Math.sqrt(num); j++) {
    if(num % j == 0){ 
      return false
    }
  }
  return true
}
var countPrimes = function(n) {
  var coun = 0
  for(var i =2; i < n; i++) {
    if(isPrimes(i)) {
      coun++
    }
  }  
  return coun
};

我们可以看到函数逻辑比较简单，内层isPrimes函数为了提高速度，给除数加了一个小于等于Math.sqrt(num)的限制，之所以可以用这个数字来做限制是因为：num = a * b 当a增大的时候b一定减小，我们假设a从1一直增加，那么b将从num一直减小，当到a = Math.sqrt(num)的时候，a == b ，如果此时a继续增大呢，a是不是就向刚才一直减小的b一样了，也就是说我们相当于把之前做的运算又从新做了一遍，而这个计算是没有意义的，所以如果一个数除到他的开跟都不能整除，基本可以判定他是一个素数了。

进阶版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var primesList = [] 
function isPrimes(num) {
  for(var j = 0; primesList[j] <= Math.sqrt(num); j++) {
    if(num % primesList[j] == 0){ 
      return false
    }
  }
  return true
}
var countPrimes = function(n) {
  var coun = 0
  for(var i =2; i < n; i++) {
    if(isPrimes(i)) {
      primesList.push(i) //给数组添加质数，丰富质数表
      coun++
    }
  }  
  return coun
};

我们看一下上面的函数，上面函数的思路是这样的：一个数（大于1），他不是质数（素数）就是合数，合数可以分解成几个质数相乘，那么我是不是只要用这个数去除以质数我就知道他是不是一个合数了，那么问题来看了，一个数我们记作A，我们只需要依次他除以[2,√A]之间的质数就能判断出来他是不是一个合数了，这样子比我们从[2,√A]，一个一个除要快很多，好了现在问题来了，我们是不是需要一个[2,√A]之间的质数表，上面的程序是这样子构建这个质数表的，从2开始，一边判断一边添加，这样子后面的数字就可以用前面的质数表了（实际上一个质数的平方是远大于紧跟在在后面的那个质数的），我们现在回到程序（其实单步跟一下程序就能看出来啦）。

1
2
3
4
if(isPrimes(i)) {
  primesList.push(i) //给数组添加质数，丰富质数表
  coun++
}1

这个语句作用是，如果发现一个数是质数就给他放到质数表里，然后在记数结果+1

1
2
3
4
5
6
7
8
function isPrimes(num) {
  for(var j = 0; primesList[j] <= Math.sqrt(num); j++) {
    if(num % primesList[j] == 0){ 
      return false
    }
  }
  return true
}

这个函数是判断函数啦，需要注意的是，第一次计算的时候primesList[0] == undefine ,num % primesList[j]的结果是NAN(我更喜欢叫他是无意义的计算)，然后NAN !== 0 （NAN连自己都相等） 这样子第一质数2，就成功的放入了数组啦
我们又成功地优化了函数，不禁要问这样子还可以优化吗？答案是：必须可以啊。

进阶版小优化

我们给上面函数的 countPrimes 函数改一下

1
2
3
4
5
6
7
8
9
10
var countPrimes = function(n) {
  var coun = 1
  for(var i =3; i < n; i+=2) {
    if(isPrimes(i)) {
      primesList.push(i) //给数组添加质数，丰富质数表
      coun++
    }
  }  
  return coun
};

我们把coun 初始值改成1，变量i从3开始，每次都往里放奇数（偶数绝逼是合数），这样子速度又快了不少

再进阶版

虽然上面的好理解，而且有了一定的优化，但是效率并不高，那么有没有效率更高的呢，答案是必须的，我们来看一下几千年前的一个算法：埃拉托斯特尼筛法
其实 埃拉托斯特尼筛法 简单的说就是，把[2,A]之间的[2,√A]的数的所有倍数全部划去，最后留下的就是质数。
那么我们是不是可以这样子生成一个大小为n的数组，数组全部都为1，每发现一个合数，我们就把一个数组的元素变为0，最后我们只需要统计1的个数就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function countPrimes(n) {
  //我们声明一个大小为n的数组，并且全部标记为1（我们把标记1是质数，0标记合数），
  var flags = new Array(n).fill(1)
  //其实这里的想法是 0 1 全不是质数，所以打掉，
  flags[0] = flags[1] = 0

  var sn = Math.sqrt(n)
  //我们只比对到[2,√A]的所有倍数
  for(var i = 2; i <= sn; i++) {
  //注意在循环里面我们已经操作了flags，所以我们此时不需要再判断划掉了的元素（flags[i] == 0） 
    if (flags[i]) {
      //注意我们这个j，埃拉托斯特尼筛法 是从数字的倍数开始划的
      for(var j = i * i; j < n; j += i) {
        flags[j] = 0
      }
    }
  }
  var count = 0
  for(var i = 0; i<n; i++) {
    if(flags[i]) {
      count++
    }
  }
  return count
}

现在我们又GET了一个新技能，我们再想一下是不是还可以优化一下，答案依然是是的，我们看一下他的进阶版

再再进阶版

如果你有心的话，你会发现我们上一个版本的函数，在划去合数的时候，会有重复划去的过程，这个我也就不上图了，自己单步走一下，或者在纸上画一下一切就会浮现出来的。
我们先上函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//小于3 就是 0 1 直接标记为0
var countPrimesx = function(n) {
  if (n < 3) {
    return 0
  }
 //数组全部置1
  var f = new Array(n).fill(true)
//有一半的数字为偶数，所以直接打掉一半，然后后面的或是为了取整
  var count = n / 2 | 0
  for(var i = 3; i * i < n; i += 2) {
    for(var j = i * i; j < n; j += 2*i) {

      if (f[j]) {
        --count
        f[j] = false
      }
    }
  }
  
  return count
}

文章末尾感谢那些愿意分享知识的人：
谢大喵
TanX的博客

感觉不错的话给博主赞助一下呗