素數判斷？這不是小學學的嗎？

您先别着急，不管您是小學，初中還是高中，從事什麼職業，我相信，堅持看完你一定有收獲！

對你有幫助别忘了給我點個贊哦~

我們要判斷素數，首先要知道素數的定義。

素數：質數又稱素數。一個大于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就足夠了

這樣我們就可以寫出這個算法的核心代碼：

int isPrime(int target) {     int i = 0;     if (target <= 1) {         printf("illegal input!\n");//素數定義         return -1;     }     for (i = 2; i < target / 2; i ) {         if (target % i == 0)             return 0;//不是素數直接返回0     }     return 1;//是素數返回1 }

1-2：再進一步

思想：在上面的基礎上，其實不需要遍曆到 n/2，隻需要到 根号n（包含根号n） 就可以了。為什麼呢？這是個數學問題，大家自行思考一下。

核心代碼：

int isPrime(int target) {     int i = 0;     if (target <= 1) {         printf("illegal input!\n");//素數定義         return -1;     }     for (i = 2; i <= sqrt(target); i ) {         if (target % i == 0)             return 0;     }     return 1; }

---

從第二種方法開始，我們都是先完成判斷素數數組，然後用二分法去查找判斷數組

這裡說一下以下三種方法牽扯的概念：

• 範圍：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：用素數表來判斷素數

思路：如果一個數不能整除比它小的任何素數，那麼這個數就是素數這種“打印”素數表的方法效率很低，不推薦使用，可以學習思想

核心代碼：

//target：輸入的要查找的數 //count：當前已知的素數個數 //PrimeArray：存放素數的數組 int isPrime(int target, int count, int* PrimeArray) {     int i = 0;     for (i = 0; i < count; i ) {         if (target % PrimeArray[i] == 0)             return 0;     }     return 1; }

---

方法3：普通篩法——埃拉托斯特尼(Eratosthenes)篩法

思路:我們的想法是，創建一個比範圍上限大1的數組，我們隻關注下标為 1 ~ N（要求的上限） 的數組元素與數組下标（一一對應）。 将數組初始化為1。然後用for循環，遍曆範圍為：【2 ~ sqrt(N)】。如果數組元素為1，則說明這個數組元素的下标所對應的數是素數。 随後我們将這個下标（除1以外）的整數倍所對應的數組元素全部置為0，也就是判斷其為非素數。這樣，我們就知道了範圍内（1 ~ 範圍上限N）所有數是素數（下标對應的數組元素值為1）或不是素數（下标對應的數組元素值為0）

用百度百科對埃拉托斯特尼篩法簡單描述：要得到自然數n以内的全部素數，必須把不大于 的所有素數的倍數剔除，剩下的就是素數。

核心代碼：

//                 判斷素數的數組    範圍上限N void Eratprime(int* isprime, int upper_board) {     int i = 0;     int j = 0;     //初始化isprime     for (i = 2; i <= upper_board; i )         isprime[i] = 1;     for (i = 2; i < sqrt(upper_board); i ) {         if (isprime[i]) {             isprime[i] = 1;         }         for (j = 2; i * j <= upper_board; j ) {//素數的n倍（n >= 2）不是素數             isprime[i * j] = 0;         }     } }

---

方法4：線性篩法——歐拉篩法

思路:我們再思考一下上面的埃拉托斯特尼篩法，會發現，在“剔除“非素數時，有些合數會重複賦值。這樣就會增加複雜度，降低效率。比如：範圍上限N = 16時2是素數，剔除”2 的倍數“，它們是：4，6， 8，10， 12， 14， 163是素數，剔除”3 的倍數”，它們是，6，9，12，156，12是重複的。如何減少重複呢？

核心代碼：

void PrimeList(int* Prime, bool* isPrime, int n) {     int i = 0;     int j = 0;     int count = 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) && (Prime[j] * (long long)i) <= N; j )//将i強制轉換是因為vs上有warning，要求轉換為寬類型防止算術溢出。數據上不産生影響             {                 isPrime[i * Prime[j]] = false;//每一個素數的 i 倍（i >= 2）都不是素數，置為false                 //這個是歐拉篩法的核心，它可以減少非素數置false的重複率                 //意義是将每一個合數（非素數）拆成 2（最小因數）與最大因數 的乘積                 if (i % Prime[j] == 0)                     break;             }         }     } }

如果你沒有理解，可以參考下例

​

​

---

感謝觀看，如果有什麼錯誤請指出，謝謝各位！

​有什麼不懂也可以直接提出來，我看到就會給大家解答的

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部