Go语言质数筛选实战（埃氏筛法详解：从零开始高效找出所有质数）

Go语言实现埃氏筛法

下面我们用Go语言一步步实现这个算法。假设我们要找出小于等于 n 的所有质数。

步骤解析：

1. 创建一个布尔数组 isPrime，长度为 n+1，初始值全部设为 true。
2. 0 和 1 不是质数，所以设置 isPrime[0] = false 和 isPrime[1] = false。
3. 从2开始遍历到 √n（因为大于 √n 的合数一定已经被更小的因数筛掉了）。
4. 如果当前数字 i 是质数（即 isPrime[i] == true），则将其所有倍数（从 i*i 开始）标记为 false。
5. 最后，遍历数组，所有值为 true 的下标即为质数。

完整Go代码实现：

package mainimport (	"fmt")// sieveOfEratosthenes 使用埃氏筛法找出小于等于n的所有质数func sieveOfEratosthenes(n int) []int {	if n < 2 {		return []int{}	}	// 创建布尔切片，初始全部为true	isPrime := make([]bool, n+1)	for i := range isPrime {		isPrime[i] = true	}	// 0和1不是质数	isPrime[0] = false	isPrime[1] = false	// 从2开始筛选	for i := 2; i*i <= n; i++ {		if isPrime[i] {			// 将i的所有倍数标记为非质数			for j := i * i; j <= n; j += i {				isPrime[j] = false			}		}	}	// 收集所有质数	primes := []int{}	for i, prime := range isPrime {		if prime {			primes = append(primes, i)		}	}	return primes}func main() {	n := 30	primes := sieveOfEratosthenes(n)	fmt.Printf("小于等于 %d 的所有质数为：%v\n", n, primes)}

运行结果

当你运行上述代码时，输出将是：

小于等于 30 的所有质数为：[2 3 5 7 11 13 17 19 23 29]

为什么埃氏筛法高效？

相比对每个数单独判断是否为质数（时间复杂度约为 O(n√n)），埃氏筛法的时间复杂度为 O(n log log n)，空间复杂度为 O(n)。对于大范围的质数筛选（如 n = 1,000,000），效率提升非常明显。

总结

通过本教程，你已经学会了如何用Go语言实现经典的埃氏筛法来高效筛选质数。这项技能不仅适用于算法面试，也能在实际项目中用于优化涉及质数计算的场景。

记住这几个SEO关键词有助于你后续搜索相关内容：Go语言质数筛选、埃氏筛法教程、Go实现埃拉托斯特尼筛、高效求质数算法。

动手试试吧！修改 n 的值，看看不同范围下的质数结果。编程的乐趣就在于实践！