国产激情综合五月久久,色综合欧美在线视频区

Go語(yǔ)言實(shí)現(xiàn)埃拉托斯特尼篩法：一個(gè)修正后的版本

花韻仙語(yǔ)

發(fā)布： 2025-07-22 17:22:01

原創(chuàng)

434人瀏覽過(guò)

go語(yǔ)言實(shí)現(xiàn)埃拉托斯特尼篩法：一個(gè)修正后的版本

本文旨在幫助開發(fā)者理解并實(shí)現(xiàn)埃拉托斯特尼篩法，用于高效地找出一定范圍內(nèi)的所有質(zhì)數(shù)。我們將分析一個(gè)存在問題的Go語(yǔ)言實(shí)現(xiàn)，找出并修復(fù)其中的錯(cuò)誤，并提供一個(gè)可正確運(yùn)行的版本，以便讀者更好地掌握該算法的原理和實(shí)現(xiàn)細(xì)節(jié)。

埃拉托斯特尼篩法簡(jiǎn)介

埃拉托斯特尼篩法是一種古老而高效的算法，用于找出給定范圍內(nèi)的所有質(zhì)數(shù)。其基本思想是從2開始，將每個(gè)質(zhì)數(shù)的倍數(shù)標(biāo)記為合數(shù)（非質(zhì)數(shù)），直到達(dá)到指定的范圍。剩余未被標(biāo)記的數(shù)字即為質(zhì)數(shù)。

問題分析與修復(fù)

原始代碼存在一個(gè)關(guān)鍵錯(cuò)誤，導(dǎo)致篩選結(jié)果不正確。錯(cuò)誤位于sieve函數(shù)內(nèi)部的內(nèi)層循環(huán)的起始條件：

for j := i; j < len(numCopy); j++ {
  if numCopy[j] % numCopy[i] != 0 || j == i {
   sievedNumbers = append(sievedNumbers, numCopy[j])
  }
}

登錄后復(fù)制

該循環(huán)從j = i開始，這意味著它會(huì)跳過(guò)numCopy[i]之前的元素，從而導(dǎo)致某些合數(shù)沒有被正確地排除。例如，當(dāng)i = 0時(shí)，numCopy[i]為2，循環(huán)應(yīng)該從j = 0開始，檢查所有元素是否能被2整除。

立即學(xué)習(xí)“go語(yǔ)言免費(fèi)學(xué)習(xí)筆記（深入）”；

正確的做法是將內(nèi)層循環(huán)的起始條件改為j = 0：

法語(yǔ)寫作助手

法語(yǔ)助手旗下的AI智能寫作平臺(tái)，支持語(yǔ)法、拼寫自動(dòng)糾錯(cuò)，一鍵改寫、潤(rùn)色你的法語(yǔ)作文。

查看詳情

for j := 0; j < len(numCopy); j++ {
  if numCopy[j] % numCopy[i] != 0 || j == i {
   sievedNumbers = append(sievedNumbers, numCopy[j])
  }
}

登錄后復(fù)制

修正后的代碼

以下是修正后的Go語(yǔ)言代碼：

package main

import "fmt"

func main() {
    primes := sieve(makeNumbers(29))
    fmt.Printf("%v\n", primes)
}

func makeNumbers(n int) []int {
    numbers := make([]int, n-1)
    for i := 0; i < len(numbers); i++ {
        numbers[i] = i + 2
    }
    return numbers
}

func sieve(numbers []int) []int {
    numCopy := numbers
    max := numbers[len(numbers)-1]
    sievedNumbers := make([]int, 0)
    for i := 0; i < len(numCopy) && numCopy[i]*numCopy[i] <= max; i++ {
        for j := 0; j < len(numCopy); j++ {
            if numCopy[j]%numCopy[i] != 0 || j == i {
                sievedNumbers = append(sievedNumbers, numCopy[j])
            }
        }
        numCopy = sievedNumbers
        sievedNumbers = make([]int, 0)
    }
    return numCopy
}

登錄后復(fù)制

代碼解釋

makeNumbers(n int) []int: 此函數(shù)生成一個(gè)包含從2到n的整數(shù)切片。
sieve(numbers []int) []int: 此函數(shù)實(shí)現(xiàn)了埃拉托斯特尼篩法。
- numCopy := numbers: 創(chuàng)建一個(gè)numbers的副本，避免修改原始切片。
- max := numbers[len(numbers)-1]: 獲取numbers切片中的最大值。
- sievedNumbers := make([]int, 0): 創(chuàng)建一個(gè)空切片，用于存儲(chǔ)篩選后的數(shù)字。
- 外層循環(huán)遍歷numCopy，直到當(dāng)前數(shù)字的平方大于max。
- 內(nèi)層循環(huán)遍歷numCopy，檢查每個(gè)數(shù)字是否能被numCopy[i]整除。如果不能整除，或者當(dāng)前數(shù)字就是numCopy[i]本身（j == i），則將該數(shù)字添加到sievedNumbers切片中。
- 循環(huán)結(jié)束后，將sievedNumbers賦值給numCopy，并清空sievedNumbers，為下一輪篩選做準(zhǔn)備。
main(): 主函數(shù)調(diào)用makeNumbers生成數(shù)字切片，然后調(diào)用sieve進(jìn)行篩選，最后打印結(jié)果。