埃拉托斯特尼篩法：加速「交叉倍數」步驟

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>

以上是埃拉托斯特尼篩法：加速「交叉倍數」步驟的詳細內容。更多資訊請關注PHP中文網其他相關文章！