算法训练营day52,204. 计数质数

204. 计数质数

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

示例 1：

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

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

提示：

• 0 <= n <= 5 * 106

//采用埃筛法解析

爱拉陶斯芬筛法，简称埃氏筛或爱氏筛。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去......。

func countPrimes(n int) int {

  count := 0

  nums := make([]int, n)

  for i := 2; i < n; i++ {

    if nums[i] == 0 {

      count++

     //剔除素数倍数

      for j := 2 * i; j < n; j += i {

        nums[j] = 1

      }

    }

  }

  return count

}