埃拉托斯特尼筛法：优化‘划去倍数’步骤

你的代码中重复划去的核心原因是：每次从2*p开始标记倍数，但这些较小的倍数其实已经被比p小的素数标记过了。比如12会被2先标记，之后又被3重复标记，完全没必要。

关键优化点 #

• 从p*p而非2*p开始划去倍数：所有小于p²的p的倍数，必然包含一个比p小的素因数，所以已经被之前的筛子处理过了。直接从p*p开始，就能避免所有重复标记操作，大幅减少CrossOffMultiples的实际执行工作量。
• 简化CrossOffMultiples函数：Go语言中切片的底层数组是引用传递的，所以不需要返回修改后的切片，直接在原切片上修改即可，减少不必要的内存拷贝和函数返回开销。

优化后的代码 #

import "math"

func ListPrimes(n int) []int {
    primeList := make([]int, 0)
    primeBooleans := SieveOfEratosthenes(n)
    for p := 0; p < n+1; p++ {
        if primeBooleans[p] {
            primeList = append(primeList, p)
        }
    }
    return primeList
}

func SieveOfEratosthenes(n int) []bool {
    if n < 2 {
        return []bool{}
    }
    primeBooleans := make([]bool, n+1)
    sqrtN := math.Sqrt(float64(n))
    for k := 2; k <= n; k++ {
        primeBooleans[k] = true
    }
    for p := 2; float64(p) <= sqrtN; p++ {
        if primeBooleans[p] {
            CrossOffMultiples(primeBooleans, p)
        }
    }
    return primeBooleans
}

func CrossOffMultiples(primeBooleans []bool, p int) {
    n := len(primeBooleans) - 1
    start := p * p
    if start > n {
        return
    }
    for k := start; k <= n; k += p {
        primeBooleans[k] = false
    }
}

优化效果说明 #

1. 避免重复标记：比如p=5时，直接从25开始标记，而不是10。10、15、20这些数已经被2或3标记过了，完全不需要再处理。
2. 减少函数开销：去掉切片返回值后，函数调用更高效，不需要额外的切片赋值操作。
3. 边界处理：增加了start > n的判断，避免当p²超过n时执行无效循环。

内容的提问来源于stack exchange，提问作者Cade Bryant