小編給大家分享一下leetcode中如何求素數(shù)，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

成都創(chuàng)新互聯(lián)專注于網(wǎng)站設(shè)計制作、成都網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計、網(wǎng)站制作、網(wǎng)站開發(fā)。公司秉持“客戶至上,用心服務(wù)”的宗旨,從客戶的利益和觀點出發(fā),讓客戶在網(wǎng)絡(luò)營銷中找到自己的駐足之地。尊重和關(guān)懷每一位客戶，用嚴謹?shù)膽B(tài)度對待客戶，用專業(yè)的服務(wù)創(chuàng)造價值，成為客戶值得信賴的朋友，為客戶解除后顧之憂。

求1——n的素數(shù)的個數(shù)，有以下三種方法：

1，遍歷法：

對于k（1

func isprime(x int) bool{    if x<=1{        return false        }    for(i:=2;i<=sqrt(x+0.5);i++){//+0.5是為了防止精度誤差        if x%i==0{           return false        }     }    return true }

此方法的問題在于許多不必要的計算，因此可以想到用空間換時間:篩選出來的素數(shù)的倍數(shù)都可以標記為合數(shù)

2，埃氏篩法

func init(){prime:=make(map[int]bool) //prime[i]為flase表示i為質(zhì)數(shù)//初始化,默認都是for(i:=2;i 

歐拉篩法優(yōu)化的一點就是改進了埃氏篩法的一點冗余：可以發(fā)現(xiàn)，在埃氏篩法中，我們對每一個n都標記了不止一次。比如10，當i=2時，10作為2的倍數(shù)被標記一次，當i=5時，10依然是5的倍數(shù)，又被多余的標記一次。

3,歐拉篩選法

歐拉篩法思想：

其基礎(chǔ)是  “任何一個合數(shù)都可以由兩個質(zhì)數(shù)相乘得到”  。那么對于每一個n我們都可以用比它小的某一個質(zhì)數(shù)來標記。

func prime(n int)int{    m:=make([]int,n)    p:=make([]int,n)    count:=0    for i:=2;i<=n;i++{        if m[i-1]==0{  // 如果未被篩過，則為素數(shù)            p[count]=i            count++        }        for j:=0;jn{                break            }            m[i * p[j]-1] = 1;     // 將已經(jīng)記錄的素數(shù)的倍數(shù)進行標記            if i % p[j] == 0{     //關(guān)鍵步驟        break            }        }    }    fmt.Println(count)    return count}

歐拉篩的難點就在于對if (i % prime[j] == 0)這步的理解，當i是prime[j]的整數(shù)倍時，記 m = i / prime[j]，那么 i * prime[j+1] 就可以變?yōu)?(m * prime[j+1]) * prime[j]，這說明 i * prime[j+1] 是 prime[j] 的整數(shù)倍，不需要再進行標記(在之后會被 prime[j] * 某個數(shù) 標記)，對于 prime[j+2] 及之后的素數(shù)同理，直接跳出循環(huán)，這樣就保證了每個合數(shù)都是被它的最小因子篩去的，避免了重復(fù)標記。

以上是“l(fā)eetcode中如何求素數(shù)”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！