素數判斷?這不是小學學的嗎?
您先別著急,不管您是小學,初中還是高中,從事什麼職業,我相信,堅持看完你一定有收穫!
[C語言必知必會]素數的判斷
我們要判斷素數,首先要知道素數的定義。
素數:質數又稱素數。一個大於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, 16
3是素數,剔除」3 的倍數」,它們是:6,9,12,15
6,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; } } }}
如果你沒有理解,可以參考下例
以上四種算法的完整代碼在我的github上,連接在下面,幫助到你了不妨給我點個star哦~
https://github.com/hairrrrr/win.ccode/tree/master/Pactise/2020WinterVacation/Prime/Prime%20Judgement
感謝觀看,如果有什麼錯誤請指出,謝謝各位!
有什麼不懂也可以直接提出來,我看到就會給大家解答的