你不知道的素數判斷方法

2020-12-05 不會編程的程序圓

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

您先別著急,不管您是小學,初中還是高中,從事什麼職業,我相信,堅持看完你一定有收穫!

[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

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

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

相關焦點

  • 素數的判斷
    O(logN)上述判斷方法,明顯存在效率極低的問題。對於每個數n,其實並不需要從2判斷到n-1我們知道,一個數若可以進行因數分解,那麼分解時得到的兩個數,一定是一個小於等於sqrt(n)和一個大於等於sqrt(n)據此,上述代碼中並不需要遍歷到n-1,遍歷到sqrt(n)即可,因為若sqrt(n)左側找不到約數,那麼右側也一定找不到約數12
  • 素數判斷算法
    return true;for (var i = 2;i <= n-1;i++) {if(num % i ==0){return false;}}return true;}方法2:上述判斷方法,明顯存在效率極低的問題。
  • 如何判斷一個數是素數呢?
    素數這個詞,我們經常在數學題中看到,判斷一個數是否是素數,首先,我們先來了解一下素數的概念,素數一般指質數。質數是指在大於1的自然數中,除了1和它本身以外不再有其他因數的自然數。了解概念之後,我們來看一道簡單的例題:判斷101到200之間的素數根據題目,我們通過編程的思想進行分析,判斷素數的方法:用一個數分別去除2到sqrt(這個數),如果能被整除, 則表明此數不是素數,反之是素數。
  • Python如何判斷一個正整數是否是素數?
    如2、3、5、7、11都是素數,因為找不到除了1和其本身之外的約數;而4、6、8都是合數,因為4可以整除2,6可以整除2和3,8可以整除2和4。而一個數的約數必然是不超過該數的,加上素數必需是只有1和本身是其約數的條件。於是,我們可以通過枚舉小於該數,並且大於1的整數,來判斷該數是否是素數。
  • C/C++每日一問--判斷素數
    特別提示:【每日一問】欄目包括但不限於【今日主題】、【實踐演練】、【知識裂變】等模塊,內容比較基礎,適合新手學習以及熟手進行知識回顧,大神勿噴,請自動繞道,謝謝!如何判斷一個數是否是素數?如何判斷一個範圍內的哪些數是素數並具體輸出素數,同時輸出個數?
  • 笑話段子:這都不知道,素數就是很樸素的數字
    A:「……」 二、以前媳婦生氣不讓我碰她,熬上半夜也要把她哄好。後來我故意惹她生氣,可得幾日安眠。 三、有一天,我在做判斷題的時候,看見素數,就問同學:「素數是什麼?」
  • 「每日一練」巧用Python判斷101-200之間有多少個素數
    大家都知道python的效率是很高的,那就讓它來幫我們處理一些複雜的數學問題吧!比如說我想要知道101-200之間有多少個素數,看看python是怎麼輸出的?案例判斷101-200之間有多少個素數,並輸出所有素數。
  • 一個奇怪的素數序列
    雕塑家安東帕森斯的「傳遞時間」素數通常被描述為數學的「原子」,或者至少是數字。素數恰好有兩個不同的因素:本身和1.(因此1不被認為是素數。)所有大於1的整數都是素數或素數的乘積。一個好奇的人類可以詢問關於素數的第一個問題是有多少,並且最早的證據之一是有無數多個素數是歐幾裡德元素的可愛論證。歐幾裡得的證明以有限的素數列表開始,並描述了一種生成不在列表中的素數的方法。
  • 「數學思維繫列」你可能不知道,小學學的素數既有趣又有用還很難
    2是最小的素數,也是唯一的偶素數,2在所有素數中的地位和價值是非常獨特的,我們已經在《你可能不知道的數字2》中進行了比較詳細的介紹。根據素數的定義和性質,任何一個自然數都可以分解為若干個素數的乘積。現在比較安全的密碼很多都是基於素數理論構建的,它主要利用了將一個非常大的整數分解為素因子是一件非常困難的事情這一特性。基於素數構建的複雜密碼體系,在有限的時間和現有的計算資源下基本是無法破解的。我們知道,任何一個自然數都可以分解為素數的乘積,如果不計因數的次序,分解形式是唯一的。這叫做算術基本定理。
  • 如何判斷一個正整數是否為質數的三種方法 | 附Python程序
    張益唐在不依賴未經證明推論的前提下,發現存在無窮多差小於7000萬的素數對,從而在孿生素數猜想這個重要問題的道路上前進了一大步。如何判斷一個正整數是否為質數?以下介紹三種判別質數的方法,並附上相應的Python程序,供有興趣的同學參考。
  • LabVIEW編程實例:如何求解1000以內的所有素數
    編程思路求解1000以內的所有素數,這個問題可以分解為下面兩個問題:如何判斷一個數是否為素數查找1000以內的所有符合條件的素數對於第一個問題,基本的判斷思路比較簡單:對於一個大於1的正整數x,如果用2到根號下x 之間的所有整數去除,均不能整除,則這樣的x可以判斷為是一個素數。
  • C語言編程求解:1到1000之間所有的素數
    算法思考:判斷一個數是不是素數,只需要判斷它是不能只能被1和自身整除。那怎麼判斷一個數不能被除1和自身之外的其他數整除呢?想法是寫一個循環,循環裡依次除以從2到這個數減1的所有的整數,如果都不能整除,說明這個數是素數;如果出現一個能整除的數,那麼這個數不是素數。(其實,判斷素數還可以優化,循環裡依次除以從2到這個數平方根的所有的整數就可以了。因為假設一個數n,除以2~根號n的整數,都不能整除,那麼除以根號n~n-1的整數也不能整數。
  • R語言中repeat循環的使用方法之素數和斐波那契數列前n項
    R語言提供了三種循環方法:for循環、while循環和repeat循環。for循環和while循環在本號前面兩篇文章已經介紹過了,這篇文章將詳細介紹repeat循環的使用方法。#求出100以內的所有素數n <- 2 #從2開始判斷repeat #循環要判斷的數字{if(n >= 100) #如果超過100,則跳出break;j <- 2 #用2~n的數j去除nrepeat #循環2~n{if(n %% j == 0
  • 如何有效尋找素數?
    如何有效尋找素數?那麼,你可知道如何才能尋找到素數呢? 取一個正整數x,如何才能找出不超過x的所有素數呢?有一種方法叫作埃拉託色尼篩法,其歷史可以上溯到古希臘時期。 埃拉託色尼篩法的步驟如下:第一步,列出從2到x的所有整數,保留2,划去所有2的倍數。
  • 素數中的數學知識:費馬二平方定理
    業餘數學之王費馬在1640年提出了一個著名的猜想:奇質數能表示為兩個平方數之和的充分必要條件是該質數被4除餘1,這就是數論中的費馬二平方定理,但費馬沒有給出嚴格的證明,一直到100年之後的1747年歐拉給出了該猜想的嚴格證明,才使得這個猜想變成了數學定理,如果你沒有一定的數論知識歐拉的巧妙證明你是很難理解的,本篇我們就來了解下該定理首先所有素數可以分成兩類
  • 素數並不孤獨
    但直到今天,對於第一次打破這個規律的N,我們仍然不知道它的具體數值,只知道它大概是個有三百多位的數。 這個例子足以說明素數可以多麼深不可測而又出人意料,同時提醒我們,面對無限,不能掉以輕心。無論有多少計算的證據,都不能輕易下定論。徵服無限的工具,只有嚴謹的數學證明。
  • 孿生素數猜想
    由於孿生素數的分布極不均勻,並且隨著數的增大變得越來越稀疏,研究孿生素數分布模式的難度也就非常之大。     在證明孿生素數猜想上的階段性成果,一般地說可以分為兩類。一類是非估算性的,這方面迄今最好的結果是1966年由中國數學家陳景潤利用篩法所取得的。他證明了:存在無窮多個素數p,使得p+2要麼是素數,要麼是兩個素數的乘積。
  • 人類已知的最大梅森素數被發現!不知道梅森數說明你沒學問
    據外媒報導,根據網際網路梅森素數大搜索Mersenne Prime Search(GIMPS)項目官方消息,來自美國佛羅裡達州的一位35歲的IT專業人士發現了人類已知的最大梅森素數
  • 【每日上機】 素數對猜想
    讓我們定義 dn 為:dn = pn+1 – pn,其中 pi 是第i個素數。顯然有 d1=1 且對於n>1有 dn 是偶數。
  • 素數大概有多少個?15歲的高斯翻過素數表之後給出了答案
    當然,高斯這位大神也對素數極度痴迷,從他十幾歲開始就研究,並且得出了重大的成果。然而,素數這個問題卻不是你研究時間長,研究人員多,就一定可以出成績的,這個跟現在的科研有著顯著不同。數學的發展史就是一部氣勢磅礴的素數研究史,但是深究下去,你更加會發現,很多素數的簡單到孩童都理解的問題都一直沒有突破。