埃拉托斯特尼筛法：加速“交叉倍数”步骤- 技术经验 -卓越飞翔博客

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

php小编苹果为您介绍埃拉托斯特尼筛法，这是一种用于快速计算素数的算法。该算法通过不断排除非素数的倍数，从而筛选出所有的素数。与传统的逐个判断素数方法相比，埃拉托斯特尼筛法能够大大加速计算过程。它的核心思想是从2开始遍历到n，将每个素数p的倍数标记为非素数，直到遍历完毕。这种方法在计算大量素数时表现出色，是一种高效的素数计算算法。

问题内容

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

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 的次数。我确信有办法做到这一点，但由于某种原因，我无法做到这一点。

有什么建议吗？

解决方法

如果您减少 CrossOffMultiples 被调用的次数，即，您不对某些素数 p 调用它，则 p * p 不会被划掉。但你可以做的是从 p * p 而不是 2 * p 开始循环。

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

问题内容

解决方法

相关推荐