2021-10-25：计数质数。统计所有小于非负整数 n 的质数的数量。力扣204。

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
}