摘要：面試官：你知道怎麼求素數嗎？我：求素數？
本文分享自華為雲社群《很多人不知道的求素數的正确方法》，原文作者：bigsai 。
前言
現在的面試官，是無數開發者的夢魇，能夠吊打面試官的屬實不多，因為大部分面試官真的有那麼那幾下子。但在面試中，我們這些小生存者不能全盤否定隻能單點突破—從某個問題上讓面試官眼前一亮。這不，今天就來分享來了。
這年頭，算法崗内卷不說，開發崗也有點内卷，對開發者要求越來越高了，而面試官也是處心積慮的“刁難” 面試者，凡是都喜歡由淺入深，凡是都喜歡問個：你知道為什麼？你知道原理嗎？之類。并且，以前隻是大廠面試官喜歡問算法，大廠員工底子好，很多甚至有 ACM 經驗或者系統刷題經驗，這很容易了解，但現在一些小公司面試官也是張口閉口 xx 算法、xx 資料結構你說說看，這不，真的被問到了。
求一個質數
在這麼一次的過程，面試官問我算法題我不吃驚，我實作早把十大排序原理、複雜度分析、代碼手寫實作出來了，也把連結清單、樹的各種操作溫習的滾瓜爛熟，不過突然就是很詫異的面試官來了一道求素數問題，我把場景還原一下：
面試官：你知道怎麼求素數嗎？
我：求素數？
面試官：是的，就是求素數。
我：這很簡單啊，判斷一個數為素數，那麼肯定就沒有兩個數(除了自身和 1)相乘等于它，隻需要枚舉看看有沒有能夠被它整除的數就可以了，如果有那麼就不是素數，如果沒有，那麼就是素數。
面試官露出一種失望的表情，說我說的對，但沒答到點子上，讓我具體說一下。
下面開始開始我的表演：
首先，最笨的方法，判斷 n 是否為素數，就是枚舉[2,n-1]之間有沒有直接能夠被 n 整除的，如果有，那麼傳回 false 這個就不是素數，否則就是素數，代碼如下：
boolean isprime(int value){
for(int i=2;i<value;i++)
{
if(value%i==0)
{return false;}
}
return true;
}
這種判斷一個素數的時間複雜度為 O(n).
但是其實這種太浪費時間了，完全沒必要這樣，可以優化一下 。如果一個數不是質數，那麼必定是兩個數的乘積，而這兩個數通常一個大一個小，并且小的小于等于根号 n，大的大于等于根号 n，我們隻需要枚舉小的可能範圍，看看是否能夠被整除，就可以判斷這個數是否為素數啦。例如
100=2*50=4*25=5*20=10*10
隻需要找 2—10 這個區間即可。右側的一定有個對應的不需要管它。
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.這種時間複雜度求單個數是 O(sqrt(n))。面試官我給你畫張圖讓你看看其中差別：
說到這裡面試官露出欣慰的笑容。
面試官：不錯不錯，基本點掌握了
我：老哥，其實求素數精髓不在這，這個太低效在很多時候，比如求小于 n 的所有素數，你看看怎麼搞？
面試官：用個數組用第二種方法求 O(n*sqrt(n))還行啊。
求多個素數
求多個素數的時候(小于 n 的素數)，上面的方法就很繁瑣了，因為有大量重複計算，因為 計算某個數的倍數 是否為素數的時候出現大量的重複計算，如果這個數比較大那麼對空間浪費比較多。
這樣，素數篩的概念就被發明和使用。篩的原理是從前往後進行一種遞推、過濾排序以來統計素數。
埃拉托斯特尼(Eratosthenes)篩法
我們看一個數如果不是為素數，那麼這個數沒有數的乘積能為它，那麼這樣我們可以根據這個思想進行操作啊：
直接從前往後枚舉，這個數位置沒被标記的肯定就是素數，如果這個數是素數那麼将這個數的倍數标記一下(下次周遊到就不需要在計算)。如果不是素數那麼就進行下一步。這樣數值越大後面計算次數越少，在進行具體操作時候可借助數組進行判斷。是以埃氏篩的核心思想就是将素數的倍數确定為合數。
假設剛開始全是素數，2 為素數，那麼 2 的倍數均不是素數；然後周遊到 3，3 的倍數标記一下；下個是 5(因為 4 已經被标記過)；一直到 n-1 為止。具體流程可以看圖：
具體代碼為：
boolean isprime[];
long prime[];
void getprime()
{
prime=new long[100001];//記錄第幾個prime
int index=0;//标記prime目前下标
isprime=new boolean [1000001];//判斷是否被标記過
for(int i=2;i<1000001;i++)
{
if(!isprime[i])
{
prime[index++]=i;
}
for(int j=i+i;j<1000000;j=j+i)//他的所有倍數都over
{
isprime[j]=true;
}
}
}
這種篩的算法複雜度為 O(nloglogn);别小瞧多的這個 logn，資料量大一個 log 可能少不少個 0，那時間也是十倍百倍甚至更多的差距。
歐拉篩
面試官已經開始點頭贊同了，哦哦的叫了起來，可其實還沒完。還有個線性篩—歐拉篩。觀察上述的埃氏篩，有很多重複的計算，尤其是前面的素數，比如 2 和 3 的最小公倍數為 6，每 3 次 2 的計算就也會遇到是 3 的倍數，而歐拉篩在埃氏篩的基礎上改進，有效的避免了這個重複計算。
具體是何種思路呢？就是埃氏篩是遇到一個質數将它的倍數計算到底，而歐拉篩則是隻用它乘以已知曉的素數的乘積進行标記，如果素數能夠被整除那就停止往後标記。
在實作上同樣也是用兩個數組，一個存儲真實有效的素數，一個用來作為标記使用。
- 在周遊到一個數的時候，如果這個數沒被标記，那麼這個數存在素數的數組中，對應下标加 1.
- 不管這個數是不是素數，周遊已知素數将它和該素數的乘積值标記，如果這個素數能夠被目前值 i 整除，那麼停止操作進行下一輪。
具體實作的代碼為：
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++){//已知素數範圍内枚舉
isprime[i * prime[j]] = true;// 标記乘積
if (i % prime[j] == 0)
break;
}
}
}
你可能會問為啥 if (i% prime[j] == 0)就要 break。
如果 i%prime[j]==0，那麼就說明 i=prime[j]*k. k 為一個整數。
那麼如果進行下一輪的話 i*prime[j+1]=(prime[j]*k)*prime[j+1]=prime[j]*(k*prime[j+1])當 i=k*prime[j+1]兩個位置就産生沖突重複計算啦,是以一旦遇到能夠被整除的就停止。
你可以看到這個過程，6 隻标記 12 而不标記 18，18 被 9*2 标記。詳細了解還需要多看看代碼想想。過程圖就不畫啦！歐拉的思路就是離我較近的我給它标記。歐拉篩的時間複雜度為 O(n)，因為每個數隻标記一次。
面試官露出一臉欣賞的表情，說了句不錯，下面就是聊聊家常，讓我等待下一次面試！