主页 / coding / 问题 / 77428119
Accepted
Cade Bryant
Asked: 2023-11-06 08:07:13 +0800 CST

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

  • 772

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

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

有什么建议么？

algorithm

1 个回答

  1. Best Answer

    如果您减少调用的次数CrossOffMultiples，即您不调用某些 prime p，那么就p * p不会被划掉。但你可以做的是开始循环而p * p不是2 * p。

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

    • 2

相关问题