2021-10-25：计数质数。统计所有小于非负整数 n 的质数的数量。力扣204。
福大大 答案2021-10-25：
自然智慧即可。从i从3开始遍历，每次加2，i*i<n。
代码用golang编写。代码如下：
代码语言：txt复制package main
import "fmt"
func main() {
n := 12
ret := countPrimes(n)
fmt.Println(ret)
}
func countPrimes(n int) int {
if n < 3 {
return 0
}
// j已经不是素数了，f[j] = true;
f := make([]bool, n)
count := n / 2 // 所有偶数都不要，还剩几个数
// 跳过了1、2 3、5、7、
for i := 3; i*i < n; i = 2 {
if f[i] {
continue
}
// 3 -> 3 * 3 = 9 3 * 5 = 15 3 * 7 = 21
// 7 -> 7 * 7 = 49 7 * 9 = 63
// 13 -> 13 * 13 13 * 15
for j := i * i; j < n; j = 2 * i {
if !f[j] {
count--
f[j] = true
}
}
}
return count
}执行结果如下：
图片左神java代码
