Go语言实现埃拉托斯特尼筛法：一个修正后的版本-小浪学习网

Go语言实现埃拉托斯特尼筛法：一个修正后的版本

本文旨在帮助开发者理解并实现埃拉托斯特尼筛法，用于高效地找出一定范围内的所有质数。我们将分析一个存在问题的go语言实现，找出并修复其中的错误，并提供一个可正确运行的版本，以便读者更好地掌握该算法的原理和实现细节。

埃拉托斯特尼筛法简介

埃拉托斯特尼筛法是一种古老而高效的算法，用于找出给定范围内的所有质数。其基本思想是从2开始，将每个质数的倍数标记为合数（非质数），直到达到指定的范围。剩余未被标记的数字即为质数。

问题分析与修复

原始代码存在一个关键错误，导致筛选结果不正确。错误位于sieve函数内部的内层循环的起始条件：

for j := i; j < len(numCopy); j++ {   if numCopy[j] % numCopy[i] != 0 || j == i {    sievedNumbers = append(sievedNumbers, numCopy[j])   } }

该循环从j = i开始，这意味着它会跳过numCopy[i]之前的元素，从而导致某些合数没有被正确地排除。例如，当i = 0时，numCopy[i]为2，循环应该从j = 0开始，检查所有元素是否能被2整除。

正确的做法是将内层循环的起始条件改为j = 0：

for j := 0; j < len(numCopy); j++ {   if numCopy[j] % numCopy[i] != 0 || j == i {    sievedNumbers = append(sievedNumbers, numCopy[j])   } }

修正后的代码

以下是修正后的Go语言代码：

package main  import "fmt"  func main() {     primes := sieve(makeNumbers(29))     fmt.Printf("%vn", primes) }  func makeNumbers(n int) []int {     numbers := make([]int, n-1)     for i := 0; i < len(numbers); i++ {         numbers[i] = i + 2     }     return numbers }  func sieve(numbers []int) []int {     numCopy := numbers     max := numbers[len(numbers)-1]     sievedNumbers := make([]int, 0)     for i := 0; i < len(numCopy) && numCopy[i]*numCopy[i] <= max; i++ {         for j := 0; j < len(numCopy); j++ {             if numCopy[j]%numCopy[i] != 0 || j == i {                 sievedNumbers = append(sievedNumbers, numCopy[j])             }         }         numCopy = sievedNumbers         sievedNumbers = make([]int, 0)     }     return numCopy }

代码解释

makeNumbers(n int) []int: 此函数生成一个包含从2到n的整数切片。
sieve(numbers []int) []int: 此函数实现了埃拉托斯特尼筛法。
- numCopy := numbers: 创建一个numbers的副本，避免修改原始切片。
- max := numbers[len(numbers)-1]: 获取numbers切片中的最大值。
- sievedNumbers := make([]int, 0): 创建一个空切片，用于存储筛选后的数字。
- 外层循环遍历numCopy，直到当前数字的平方大于max。
- 内层循环遍历numCopy，检查每个数字是否能被numCopy[i]整除。如果不能整除，或者当前数字就是numCopy[i]本身（j == i），则将该数字添加到sievedNumbers切片中。
- 循环结束后，将sievedNumbers赋值给numCopy，并清空sievedNumbers，为下一轮筛选做准备。
main(): 主函数调用makeNumbers生成数字切片，然后调用sieve进行筛选，最后打印结果。