埃拉托斯特尼筛法：加速“交叉倍数”步骤

Question

我已经实现了一个使用埃拉托斯特尼筛法算法列出素数的函数，如下（使用Go）：

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

func SieveOfEratosthenes(n int) []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] == true {
            primeBooleans = CrossOffMultiples(primeBooleans, p)
        }
    }
    return primeBooleans
}

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

但我发现了一个低效率的地方：即，

CrossOffMultiples

被调用的次数超过了必要的次数。 IOW，已经被“划掉”的整数将被划掉第二次或第三次（甚至更多次），因为任何倍数

m

都会有多个因素来划分它。但我似乎无法弄清楚如何利用这些信息来减少调用

CrossOffMultiples

的次数。我确信有办法做到这一点，但由于某种原因，我无法做到这一点。

有什么建议吗？

Answer 1

如果减少调用

CrossOffMultiples

的次数，即，对于某些素数

p

不调用它，那么

p * p

不会被划掉。但你可以做的是从

p * p

而不是

2 * p

开始循环。

多次划掉数字是正常的，埃拉托斯特尼筛法就是这么做的。 线性筛法是您可能感兴趣的类似算法。