素數判斷？這不是小學學的嗎？
您先彆著急，不管您是小學，初中還是高中，從事什麼職業，我相信，堅持看完你一定有收穫！
我們要判斷素數，首先要知道素數的定義。
素數：質數又稱素數。一個大於1的自然數，除了1和它自身外，不能被其他自然數整除的數叫做質數;否則稱為合數。
知道了素數的定義，那麼我們應該想一下，如何去判斷一個數是否為素數？
一種思路是，我們在每次得到一個數後，都去計算，去嘗試因式分解它，看它除了1和自身之外還有沒有其他因子另一種是，我們去查閱素數表，看這個數在不在素數表上。那我們就要先得到素數表。
以下除了第一種方法，第2~4種方法都是用第二種思路做的當要判斷的目標數很少時，第一種高效。但是當給定的目標數組很多，數也很大時。後面的思路配上高效的查找算法，顯然更高效
方法1：暴力求解
1-1:稍微動動腦
思想：根據素數的定義思考。素數是大於1的自然數，除了1和自身外，其他數都不是它的因子。 那我們就可以用一個循環，從2開始遍歷到這個數減去1，如果這個數都不能被整除，那麼這個數就是素數。 也就是說： 給定一個數 n , i 從 2 開始取值，直到 n - 1(取整數),如果 n % i != 0 , n 就是素數 進一步思考，有必要遍歷到 n - 1 嗎？ 除了1以外，任何合數最小的因子就是2，那最大的因子就是 n/2 那我們就遍歷到 n/2就足夠了
這樣我們就可以寫出這個算法的核心代碼：
<code>intisPrime(inttarget){
inti=0;
if(target<=1){
printf("illegalinput!\\n");//素數定義
return-1;
}
for(i=2;i<target>if(target%i==0)
return0;//不是素數直接返回0
}
return1;//是素數返回1
}
/<target>/<code> 1-2：再進一步
思想：在上面的基礎上，其實不需要遍歷到 n/2，只需要到 根號n（包含根號n） 就可以了。為什麼呢？這是個數學問題，大家自行思考一下。
核心代碼：
<code>intisPrime(inttarget){
inti=0;
if(target<=1){
printf("illegalinput!\\n");//素數定義
return-1;
}
for(i=2;i<=sqrt(target);i++){
if(target%i==0)
return0;
}
return1;
}
/<code>
從第二種方法開始，我們都是先完成判斷素數數組，然後用二分法去查找判斷數組
這裡說一下以下三種方法牽扯的概念：
- 範圍：1 ~ 範圍上限N
- 範圍上限N：判斷素數需要用戶輸入隨機素數，這個隨機素數的範圍是1 ~ N
- 判斷素數數組：將數組的下標與1 ~ N的自然數一一對應起來。判斷 1到N 的自然數是否為素數，其實就是判斷數組的下標是否為素數，如果是 給這個下標所對應的判斷素數數組元素賦1，否則賦0比如：我要判斷3是否為素數，我們就找到判斷素數數組isPrime中的下標為3的元素，即：isPrime[3]如果 3 是素數 isPrime[3] = 1否則 isPrime[3] = 0這樣我們在用二分法查找時，查找數組下標就可以，找到下標後返回下標對應的判斷素數數組的值。如果是1說明下標對應的自然數是素數，否則不是
方法2：用素數表來判斷素數
思路：如果一個數不能整除比它小的任何素數，那麼這個數就是素數這種“打印”素數表的方法效率很低，不推薦使用，可以學習思想
核心代碼：
<code>//target：輸入的要查找的數
//count：當前已知的素數個數
//PrimeArray：存放素數的數組
intisPrime(inttarget,intcount,int*PrimeArray){
inti=0;
for(i=0;i<count>if(target%PrimeArray[i]==0)
return0;
}
return1;
}
/<count>/<code>
方法3：普通篩法——埃拉託斯特尼(Eratosthenes)篩法
思路:我們的想法是，創建一個比範圍上限大1的數組，我們只關注下標為 1 ~ N（要求的上限） 的數組元素與數組下標（一一對應）。 將數組初始化為1。然後用for循環，遍歷範圍為：【2 ~ sqrt(N)】。如果數組元素為1，則說明這個數組元素的下標所對應的數是素數。 隨後我們將這個下標（除1以外）的整數倍所對應的數組元素全部置為0，也就是判斷其為非素數。這樣，我們就知道了範圍內（1 ~ 範圍上限N）所有數是素數（下標對應的數組元素值為1）或不是素數（下標對應的數組元素值為0）
用百度百科對埃拉託斯特尼篩法簡單描述：要得到自然數n以內的全部素數，必須把不大於 的所有素數的倍數剔除，剩下的就是素數。
核心代碼：
<code>//判斷素數的數組範圍上限N
voidEratprime(int*isprime,intupper_board){
inti=0;
intj=0;
//初始化isprime
for(i=2;i<=upper_board;i++)
isprime[i]=1;
for(i=2;i<sqrt>if(isprime[i]){
isprime[i]=1;
}
for(j=2;i*j<=upper_board;j++){//素數的n倍（n>=2）不是素數
isprime[i*j]=0;
}
}
}
/<sqrt>/<code>
方法4：線性篩法——歐拉篩法
思路 :我們再思考一下上面的埃拉託斯特尼篩法，會發現，在“剔除“非素數時，有些合數會重複賦值。這樣就會增加複雜度，降低效率。比如：範圍上限N = 16時2是素數，剔除”2 的倍數“，它們是：4，6， 8，10， 12， 14， 163是素數，剔除”3 的倍數”，它們是，6，9，12，156，12是重複的。如何減少重複呢？
核心代碼：
<code>voidPrimeList(int*Prime,bool*isPrime,intn){
inti=0;
intj=0;
intcount=0;
if(isPrime!=NULL){//確保isPrime不是空指針
//將isPrime數組初始化為1
for(i=2;i<=N;i++){
isPrime[i]=true;
}
}
if(isPrime!=NULL&&Prime!=NULL){
//從2遍歷到範圍上限N
for(i=2;i<=N;i++){
if(isPrime[i])//如果下標（下標對應著1~範圍上限N）對應的isPrime值沒有被置為false，說明這個數是素數，將下標放入素數數組
Prime[count++]=i;
//循環控制表達式的意義：j小於等於素數數組的個數或素數數組中的每一個素數與 i 的積小於範圍上限N
for(j=0;(j<count>{
isPrime[i*Prime[j]]=false;//每一個素數的i倍（i>=2）都不是素數，置為false
//這個是歐拉篩法的核心，它可以減少非素數置false的重複率
//意義是將每一個合數（非素數）拆成2（最小因數）與最大因數的乘積
if(i%Prime[j]==0)
break;
}
}
}
}
/<count>/<code>如果你沒有理解，可以參考下例
感謝觀看，如果有什麼錯誤請指出，謝謝各位！
有什麼不懂也可以直接提出來，我看到就會給大家解答的
閱讀更多 編程反思錄 的文章
