埃氏筛

数学与数论

说明

从每个素数的平方开始标记倍数；生成不超过 n 的素数。

分析

从 2 起遍历候选数，若尚未被标记，就把它当成素数并标记从 p² 开始的倍数。更小的倍数已被较小素数处理，无需重复。

图解推演

求 20 以内素数：2 标记 4、6、8…20；3 从 9 开始标记 9、12、15、18。到 5 时 5² 已超过 20，无需继续筛除。剩余 2、3、5、7、11、13、17、19 为素数，0 和 1 必须事先排除。

查看图表代码

适用前提与边界

预处理时间约 O(n log log n)、空间 O(n)，适合一次求出范围内许多素数。

示例输入与调用

fmt.Println(Primes(20))

运行输出

[2 3 5 7 11 13 17 19]

完整 Go 示例

package main

import "fmt"

func Primes(n int) []int {
	composite := make([]bool, n+1)
	for p := 2; p <= n/p; p++ {
		if !composite[p] {
			for x := p * p; x <= n; x += p {
				composite[x] = true
			}
		}
	}
	out := []int{}
	for p := 2; p <= n; p++ {
		if !composite[p] {
			out = append(out, p)
		}
	}
	return out
}

func main() {
	fmt.Println(Primes(20))
}