埃氏筛

简介和实现

从 2 开始，将每个素数的倍数，标记成合数。一个素数 $q$ 的各个倍数，是一个差为 $q$ 的等差数列。注意对于一个新的被迭代到的素数 $n$，其第一个应该标记的倍数不必从 $n$ 开始，而是可以优化成 $n^2$，因为 $2n,3n,4n...(n−1)n$ 已经分别在迭代小于 $n$ 的其他素数时被标记了

下面的代码返回严格小于 $n$ 的所有素数的数目

func countPrimes(n int) int {
    // find the number of all primes < n strictly
	ans := 0
	np := make([]bool, n)
	for i := 0; i < n; i++ {
		np[i] = true
	}
	for i := 2; i * i < n; i++ {
		if np[i] {
			ans++
			for j := i * i; j < n; j += i {
				np[j] = false
			}
		}
	}
	return ans
}

时间复杂度证明TODO