日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
面試官本想拿一道求素?cái)?shù)搞我，但被我優(yōu)雅的"回?fù)?了

本文轉(zhuǎn)載自微信公眾號(hào)「 bigsai」，作者 bigsai。轉(zhuǎn)載本文請聯(lián)系 bigsai公眾號(hào)。

網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)建站！專注于網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、微信平臺(tái)小程序開發(fā)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了桓仁免費(fèi)建站歡迎大家使用！

前言

現(xiàn)在的面試官，是無數(shù)開發(fā)者的夢魘，能夠吊打面試官的屬實(shí)不多，因?yàn)榇蟛糠置嬖嚬僬娴挠心敲茨菐紫伦印５诿嬖囍?，我們這些小生存者不能全盤否定只能單點(diǎn)突破—從某個(gè)問題上讓面試官眼前一亮。這不，今天就來分享來了。

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

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

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

面試官：你知道怎么求素?cái)?shù)嗎?

我：求素?cái)?shù)?

面試官：是的，就是求素?cái)?shù)。

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

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

下面開始開始我的表演：

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

 
 
 
 
    
  
  
  
  
  1. boolean isprime(int value){ 
    2. 
  
  
  
  
  2.   for(int i=2;i
  
  
  
  
  3.   { 
    4. 
  
  
  
  
  4.        if(value%i==0) 
    5. 
  
  
  
  
  5.        {return false;} 
    6. 
  
  
  
  
  6.   } 
    7. 
  
  
  
  
  7.     return true; 
    8. 
  
  
  
  
  8. } 
    9.

這種判斷一個(gè)素?cái)?shù)的時(shí)間復(fù)雜度為O(n).

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

 
 
 
 
    
  
  
  
  
  1. boolean isprime(int value) 
    2. 
  
  
  
  
  2. { 
    3. 
  
  
  
  
  3.   for(int i=2;i*i
  
  
  
  
  4.     { 
    5. 
  
  
  
  
  5.        if(value%i==0) 
    6. 
  
  
  
  
  6.        {return false;} 
    7. 
  
  
  
  
  7.     } 
    8. 
  
  
  
  
  8.     return true; 
    9. 
  
  
  
  
  9. } 
    10.

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

2

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

面試官：不錯(cuò)不錯(cuò)，基本點(diǎn)掌握了

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

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

求多個(gè)素?cái)?shù)

求多個(gè)素?cái)?shù)的時(shí)候(小于n的素?cái)?shù))，上面的方法就很繁瑣了，因?yàn)橛写罅恐貜?fù)計(jì)算，因?yàn)?計(jì)算某個(gè)數(shù)的倍數(shù) 是否為素?cái)?shù)的時(shí)候出現(xiàn)大量的重復(fù)計(jì)算，如果這個(gè)數(shù)比較大那么對(duì)空間浪費(fèi)比較多。

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

埃拉托斯特尼(Eratosthenes)篩法

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

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

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

具體代碼為：

 
 
 
 
    
  
  
  
  
  1. boolean isprime[]; 
    2. 
  
  
  
  
  2. long prime[]; 
    3. 
  
  
  
  
  3. void getprime() 
    4. 
  
  
  
  
  4. { 
    5. 
  
  
  
  
  5.         prime=new long[100001];//記錄第幾個(gè)prime 
    6. 
  
  
  
  
  6.       int index=0;//標(biāo)記prime當(dāng)前下標(biāo) 
    7. 
  
  
  
  
  7.         isprime=new boolean [1000001];//判斷是否被標(biāo)記過 
    8. 
  
  
  
  
  8.         for(int i=2;i<1000001;i++) 
    9. 
  
  
  
  
  9.         { 
    10. 
  
  
  
  
  10.             if(!isprime[i]) 
    11. 
  
  
  
  
  11.             { 
    12. 
  
  
  
  
  12.                 prime[index++]=i; 
    13. 
  
  
  
  
  13.             } 
    14. 
  
  
  
  
  14.             for(int j=i+i;j<1000000;j=j+i)//他的所有倍數(shù)都o(jì)ver 
    15. 
  
  
  
  
  15.             { 
    16. 
  
  
  
  
  16.                 isprime[j]=true;                     
    17. 
  
  
  
  
  17.             } 
    18. 
  
  
  
  
  18.         } 
    19. 
  
  
  
  
  19. } 
    20.

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

歐拉篩

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

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

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

  • 在遍歷到一個(gè)數(shù)的時(shí)候，如果這個(gè)數(shù)沒被標(biāo)記，那么這個(gè)數(shù)存在素?cái)?shù)的數(shù)組中，對(duì)應(yīng)下標(biāo)加1.
  • 不管這個(gè)數(shù)是不是素?cái)?shù)，遍歷已知素?cái)?shù)將它和該素?cái)?shù)的乘積值標(biāo)記，如果這個(gè)素?cái)?shù)能夠被當(dāng)前值i整除，那么停止操作進(jìn)行下一輪。

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

 
 
 
 
    
  
  
  
  
  1. boolean isprime[]; 
    2. 
  
  
  
  
  2. int prime[]; 
    3. 
  
  
  
  
  3. void getprimeoula()// 歐拉篩 
    4. 
  
  
  
  
  4. { 
    5. 
  
  
  
  
  5.         prime = new int[100001];// 記錄第幾個(gè)prime 
    6. 
  
  
  
  
  6.         int index = 0; 
    7. 
  
  
  
  
  7.         isprime = new boolean[1000001]; 
    8. 
  
  
  
  
  8.         for (int i = 2; i < 1000001; i++) { 
    9. 
  
  
  
  
  9.             if (!isprime[i]) { 
    10. 
  
  
  
  
  10.                 prime[index++] = i; 
    11. 
  
  
  
  
  11.             } 
    12. 
  
  
  
  
  12.             for (int j = 0; j < index && i * prime[j] <= 100000; j++){//已知素?cái)?shù)范圍內(nèi)枚舉 
    13. 
  
  
  
  
  13.                 isprime[i * prime[j]]= true;// 標(biāo)記乘積 
    14. 
  
  
  
  
  14.                 if (i % prime[j] == 0) 
    15. 
  
  
  
  
  15.                     break; 
    16. 
  
  
  
  
  16.             } 
    17. 
  
  
  
  
  17.         } 
    18. 
  
  
  
  
  18. } 
    19.

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

如果i%prime[j]==0，那么就說明i=prime[j]*k. k為一個(gè)整數(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]兩個(gè)位置就產(chǎn)生沖突重復(fù)計(jì)算啦,所以一旦遇到能夠被整除的就停止。

image-20201208121324157

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

面試官露出一臉欣賞的表情，說了句不錯(cuò)，下面就是聊聊家常，讓我等待下一次面試!


本文題目：面試官本想拿一道求素?cái)?shù)搞我，但被我優(yōu)雅的"回?fù)?了
分享路徑：http://www.dlmjj.cn/article/djdsdoi.html