README.md

204. 计数质数

题目描述

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

示例:

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

解题思路

1. hash table
2. i的倍数不可能为素数

具体解法

Golang

func countPrimes(n int) int {
	if n < 3 {
		return 0
	}
	var count int
	fMap := make(map[int]bool)
	for i := 2; i < n; i++ {
		if fMap[i] {
			continue
		}
		count++
		fMap[i] = false
		// i的倍数不可能为素数
		for j := 2 * i; j < n; j += i {
			fMap[j] = true
		}
	}
	return count
}