博客

题目

：统计所有小于非负整数 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))
}

提交截图

：