怎么求素數(shù)

這篇文章主要講解了“怎么求素數(shù)”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“怎么求素數(shù)”吧！

10年積累的做網(wǎng)站、成都網(wǎng)站建設(shè)經(jīng)驗，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識你，你也不認(rèn)識我。但先網(wǎng)站設(shè)計后付款的網(wǎng)站建設(shè)流程，更有黃驊免費網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

前言

現(xiàn)在的面試官，是無數(shù)開發(fā)者的夢魘，能夠吊打面試官的屬實不多，因為大部分面試官真的有那么那幾下子。但在面試中，我們這些小生存者不能全盤否定只能單點突破—從某個問題上讓面試官眼前一亮。這不，今天就來分享來了。

這年頭，算法崗內(nèi)卷不說，開發(fā)崗也有點內(nèi)卷，對開發(fā)者要求越來越高了，而面試官也是處心積慮的 "刁難"  面試者，凡是都喜歡由淺入深，凡是都喜歡問個：你知道為什么?你知道原理嗎?之類。并且，以前只是大廠面試官喜歡問算法，大廠員工底子好，很多甚至有ACM經(jīng)驗或者系統(tǒng)刷題經(jīng)驗，這很容易理解，但現(xiàn)在一些小公司面試官也是張口閉口  xx算法、xx數(shù)據(jù)結(jié)構(gòu)你說說看，這不，真的被問到了。

求一個質(zhì)數(shù)

在這么一次的過程，面試官問我算法題我不吃驚，我實現(xiàn)早把十大排序原理、復(fù)雜度分析、代碼手寫實現(xiàn)出來了，也把鏈表、樹的各種操作溫習(xí)的滾瓜爛熟，不過突然就是很詫異的面試官來了一道求素數(shù)問題，我把場景還原一下：

面試官：你知道怎么求素數(shù)嗎?

我：求素數(shù)?

面試官：是的，就是求素數(shù)。

我：這很簡單啊，判斷一個數(shù)為素數(shù)，那么肯定就沒有兩個數(shù)(除了自身和1)相乘等于它，只需要枚舉看看有沒有能夠被它整除的數(shù)就可以了，如果有那么就不是素數(shù)，如果沒有，那么就是素數(shù)。

面試官露出一種失望的表情，說我說的對，但沒答到點子上，讓我具體說一下。

下面開始開始我的表演：

首先，最笨的方法，判斷n是否為素數(shù)，就是枚舉[2,n-1]之間有沒有直接能夠被n整除的，如果有，那么返回false這個就不是素數(shù)，否則就是素數(shù)，代碼如下：

boolean isprime(int value){   for(int i=2;i<value;i++)   {        if(value%i==0)        {return false;}   }     return true; }

這種判斷一個素數(shù)的時間復(fù)雜度為O(n).

但是其實這種太浪費時間了，完全沒必要這樣，可以優(yōu)化一下  。如果一個數(shù)不是質(zhì)數(shù)，那么必定是兩個數(shù)的乘積，而這兩個數(shù)通常一個大一個小，并且小的小于等于根號n，大的大于等于根號n，我們只需要枚舉小的可能范圍，看看是否能夠被整除，就可以判斷這個數(shù)是否為素數(shù)啦。例如100=2*50=4*25=5*20=10*10  只需要找2&mdash;10這個區(qū)間即可。右側(cè)的一定有個對應(yīng)的不需要管它。

boolean isprime(int value) {   for(int i=2;i*i<value+1;i++)     {        if(value%i==0)        {return false;}     }     return true; }

這里之所以要小于value+1，就是要包含根號的情況，例如  3*3=9.要包含3.這種時間復(fù)雜度求單個數(shù)是O(logn)。面試官我給你畫張圖讓你看看其中區(qū)別：

怎么求素數(shù)

2

說到這里面試官露出欣慰的笑容。

面試官：不錯不錯，基本點掌握了

我：老哥，其實求素數(shù)精髓不在這，這個太低效在很多時候，比如求小于n的所有素數(shù)，你看看怎么搞?

面試官：用個數(shù)組用第二種方法求nlogn還行啊。

求多個素數(shù)

求多個素數(shù)的時候(小于n的素數(shù))，上面的方法就很繁瑣了，因為有大量重復(fù)計算，因為 計算某個數(shù)的倍數(shù)  是否為素數(shù)的時候出現(xiàn)大量的重復(fù)計算，如果這個數(shù)比較大那么對空間浪費比較多。

這樣，素數(shù)篩的概念就被發(fā)明和使用。篩的原理是從前往后進(jìn)行一種遞推、過濾排序以來統(tǒng)計素數(shù)。

埃拉托斯特尼(Eratosthenes)篩法

我們看一個數(shù)如果不是為素數(shù)，那么這個數(shù)沒有數(shù)的乘積能為它，那么這樣我們可以根據(jù)這個思想進(jìn)行操作?。?/p>

直接從前往后枚舉，這個數(shù)位置沒被標(biāo)記的肯定就是素數(shù)，如果這個數(shù)是素數(shù)那么將這個數(shù)的倍數(shù)標(biāo)記一下(下次遍歷到就不需要在計算)。如果不是素數(shù)那么就進(jìn)行下一步。這樣數(shù)值越大后面計算次數(shù)越少，在進(jìn)行具體操作時候可借助數(shù)組進(jìn)行判斷。所以埃氏篩的核心思想就是將素數(shù)的倍數(shù)確定為合數(shù)。

假設(shè)剛開始全是素數(shù)，2為素數(shù)，那么2的倍數(shù)均不是素數(shù);然后遍歷到3，3的倍數(shù)標(biāo)記一下;下個是5(因為4已經(jīng)被標(biāo)記過);一直到n-1為止。具體流程可以看圖：

怎么求素數(shù)

具體代碼為：

boolean isprime[]; long prime[]; void getprime() {         prime=new long[100001];//記錄第幾個prime       int index=0;//標(biāo)記prime當(dāng)前下標(biāo)         isprime=new boolean [1000001];//判斷是否被標(biāo)記過         for(int i=2;i<1000001;i++)         {             if(!isprime[i])             {                 prime[index++]=i;             }             for(int j=i+i;j<1000000;j=j+i)//他的所有倍數(shù)都o(jì)ver             {                 isprime[j]=true;                                 }         } }

這種篩的算法復(fù)雜度為O(nloglogn);別小瞧多的這個logn，數(shù)據(jù)量大一個log可能少不少個0，那時間也是十倍百倍甚至更多的差距。

歐拉篩

面試官已經(jīng)開始點頭贊同了，哦哦的叫了起來，可其實還沒完。還有個線性篩&mdash;歐拉篩。觀察上述的埃氏篩，有很多重復(fù)的計算，尤其是前面的素數(shù)，比如2和3的最小公倍數(shù)為6，每3次2的計算就也會遇到是3的倍數(shù)，而歐拉篩在埃氏篩的基礎(chǔ)上改進(jìn)，有效的避免了這個重復(fù)計算。

具體是何種思路呢?就是埃氏篩是遇到一個質(zhì)數(shù)將它的倍數(shù)計算到底，而歐拉篩則是只用它乘以已知曉的素數(shù)的乘積進(jìn)行標(biāo)記，如果素數(shù)能夠被整除那就停止往后標(biāo)記。

在實現(xiàn)上同樣也是用兩個數(shù)組，一個存儲真實有效的素數(shù)，一個用來作為標(biāo)記使用。

  • 在遍歷到一個數(shù)的時候，如果這個數(shù)沒被標(biāo)記，那么這個數(shù)存在素數(shù)的數(shù)組中，對應(yīng)下標(biāo)加1.

  • 不管這個數(shù)是不是素數(shù)，遍歷已知素數(shù)將它和該素數(shù)的乘積值標(biāo)記，如果這個素數(shù)能夠被當(dāng)前值i整除，那么停止操作進(jìn)行下一輪。

具體實現(xiàn)的代碼為：

boolean isprime[]; int prime[]; void getprimeoula()// 歐拉篩 {         prime = new int[100001];// 記錄第幾個prime         int index = 0;         isprime = new boolean[1000001];         for (int i = 2; i < 1000001; i++) {             if (!isprime[i]) {                 prime[index++] = i;             }             for (int j = 0; j < index && i * prime[j] <= 100000; j++){//已知素數(shù)范圍內(nèi)枚舉                 isprime[i * prime[j]] = true;// 標(biāo)記乘積                 if (i % prime[j] == 0)                     break;             }         } }

你可能會問為啥if (i % prime[j] == 0)就要break。

如果i%prime[j]==0，那么就說明i=prime[j]*k. k為一個整數(shù)。

那么如果進(jìn)行下一輪的話

i*prime[j+1]=(prime[j]*k)*prime[j+1]=prime[j]*(k*prime[j+1])  當(dāng)i=k*prime[j+1]兩個位置就產(chǎn)生沖突重復(fù)計算啦,所以一旦遇到能夠被整除的就停止。

怎么求素數(shù)

image-20201208121324157

你可以看到這個過程，6只標(biāo)記12而不標(biāo)記18，18被9*2標(biāo)記。詳細(xì)理解還需要多看看代碼想想。過程圖就不畫啦!歐拉的思路就是離我較近的我給它標(biāo)記。歐拉篩的時間復(fù)雜度為O(n)，因為每個數(shù)只標(biāo)記一次。

感謝各位的閱讀，以上就是“怎么求素數(shù)”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對怎么求素數(shù)這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！

文章名稱：怎么求素數(shù)
網(wǎng)站URL：http://bm7419.com/article8/igcpip.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站設(shè)計、網(wǎng)站改版、定制網(wǎng)站、移動網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作、ChatGPT

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

成都網(wǎng)頁設(shè)計公司