溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下leetcode中如何求素數，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
求1——n的素數的個數，有以下三種方法：
1，遍歷法：
對于k（1<k<=n）;判斷k 是否可以被 2到sqrt（k）的整數整除
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 }
此方法的問題在于許多不必要的計算，因此可以想到用空間換時間:篩選出來的素數的倍數都可以標記為合數
2，埃氏篩法
func init(){prime:=make(map[int]bool) //prime[i]為flase表示i為質數//初始化,默認都是for(i:=2;i<maxn;i++){ if !prime[i]{ for j:=2*i;j<maxn;j+=i){//把所有i的倍數都進行標記 prime[j]=true; } } }}
歐拉篩法優化的一點就是改進了埃氏篩法的一點冗余：可以發現，在埃氏篩法中，我們對每一個n都標記了不止一次。比如10，當i=2時，10作為2的倍數被標記一次，當i=5時，10依然是5的倍數，又被多余的標記一次。
3,歐拉篩選法
歐拉篩法思想：
其基礎是 “任何一個合數都可以由兩個質數相乘得到” 。那么對于每一個n我們都可以用比它小的某一個質數來標記。
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{ // 如果未被篩過，則為素數 p[count]=i count++ } for j:=0;j<count;j++{ if i*p[j]>n{ break } m[i * p[j]-1] = 1; // 將已經記錄的素數的倍數進行標記 if i % p[j] == 0{ //關鍵步驟 break } } } fmt.Println(count) return count}
歐拉篩的難點就在于對if (i % prime[j] == 0)這步的理解，當i是prime[j]的整數倍時，記 m = i / prime[j]，那么 i * prime[j+1] 就可以變為 (m * prime[j+1]) * prime[j]，這說明 i * prime[j+1] 是 prime[j] 的整數倍，不需要再進行標記(在之后會被 prime[j] * 某個數 標記)，對于 prime[j+2] 及之后的素數同理，直接跳出循環，這樣就保證了每個合數都是被它的最小因子篩去的，避免了重復標記。
以上是“leetcode中如何求素數”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
