leetcode中如何求素?cái)?shù)

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

求1——n的素?cái)?shù)的個(gè)數(shù)，有以下三種方法：

1，遍歷法：

對(duì)于k（1<k<=n）;判斷k 是否可以被 2到sqrt（k）的整數(shù)整除

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 }

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

2，埃氏篩法

func init(){prime:=make(map[int]bool) //prime[i]為flase表示i為質(zhì)數(shù)//初始化,默認(rèn)都是for(i:=2;i<maxn;i++){        if !prime[i]{            for j:=2*i;j<maxn;j+=i){//把所有i的倍數(shù)都進(jìn)行標(biāo)記                        prime[j]=true;            }    }  }}

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

3,歐拉篩選法

歐拉篩法思想：

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

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{  // 如果未被篩過，則為素?cái)?shù)            p[count]=i            count++        }        for j:=0;j<count;j++{            if i*p[j]>n{                break            }            m[i * p[j]-1] = 1;     // 將已經(jīng)記錄的素?cái)?shù)的倍數(shù)進(jìn)行標(biāo)記            if i % p[j] == 0{     //關(guān)鍵步驟        break            }        }    }    fmt.Println(count)    return count}

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

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