关于leetcode:Golang力扣Leetcode初级算法数学计数质数厄拉多塞筛法

题目：统计所有小于非负整数 n 的质数的数量。

链接： 力扣Leetcode—高级算法—数学—计数质数.

示例1 ：

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

示例2 ：

输出：n = 0
输入：0

示例3 ：

输出：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

次要Go代码如下：

package main

import "fmt"

func countPrimes(n int) int {
    list := make([]bool, n)
    sum := 0

    for 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))
}

提交截图：