【[Golang]力扣Leetcode—初级算法—数学—计数质数（厄拉多塞筛法）】题目：统计所有小于非负整数 n 的质数的数量。
链接： 力扣Leetcode—初级算法—数学—计数质数.
示例1 ：
输入：n = 10示例2 ：
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
输入：n = 0示例3 ：
输出：0
输入：n = 1标签：数组、数学、枚举、数论
输出：0
思路：如果用暴力破解，那么毫无疑问会超时，我们可以用厄拉多塞筛法（Eratosthenes）：即从2开始，2的倍数全部去掉；接下来3是质数，3的倍数全部去掉，如此下去，留下的都是质数。
- 我们首先定义一个长度为n的bool数组，用来标识某个数是否是素数，如果不是素数就将数组中对应的位置置为true
- 首先，0和1肯定不是质数，所以数组前两个元素的值置为true
- 数组中初始化的时候每个元素对应的值都是false，从2开始，如果对应数组中的值还是false，那么说明了这个数一定是质数
- 所以2是质数，那么将2翻倍的数一定不是质数，所以我们将2一直这样翻倍翻下去，直到某一个倍数超过n，那么数组中就没有对应的位置了，我们在这个过程中，将翻倍得到的数字在数组中对应的位置置为true
- 然后遍历2的下一个数，首先看这个数在数组中对应位置的值是true还是false，如果是true说明了这个位置是由前面某个数翻倍得到的，说明他是合数，所以跳过，如果是false，说明了这个数不能由前面的数翻倍得到，那么他肯定是质数
- 一直重复上述过程，直到这个2变成了最后的n
package mainimport "fmt"func countPrimes(n int) int {
list := make([]bool, n)
sum := 0for i := 2;
i < n;
i++ {
if list[i] == false {
sum++
}
for j := i + i;
j < n;
j += i {
list[j] = true
}
}
return sum
}func main() {
var n int
fmt.Scanf("%d", &n)
fmt.Println(countPrimes(n))
}提交截图：
![[Golang]力扣Leetcode—初级算法—数学—计数质数（厄拉多塞筛法）](https://img.it610.com/image/info9/41b09e044e044fca942d1c9ac7c8f6a1.jpg)
文章图片
