查找質數公式?先列舉一個口算方法：假設計算120以内的質數可以把2、3、5、7先列出來，然後從6開始往後，每次加6得一偶數（12、18、24…）,然後計算該偶數的相鄰奇數是否是質數，計算方法是，首先将個位為5（比如25）的奇數直接pass，在49之前隻需計算能否被3整除，即11、13（12的相鄰奇數）、17、19（18的相鄰奇數）、23（24的相鄰奇數，pass掉25）、29、31（30的相鄰奇數）、37（36的相鄰奇數pass掉35）、41、43（42的相鄰奇數）、47（48的相鄰奇數）隻需計算能否被3整除；在48之後121之前的6的倍數的相鄰奇數隻需計算能否被3、7整除（比如113=114-1隻需計算能否被3、7整除），3、7都不能整除就是質數（延伸：121=11*11至168=13*13-1則隻需要計算3、7、11……），今天小編就來聊一聊關于查找質數公式?接下來我們就一起去研究一下吧!

查找質數公式

先列舉一個口算方法：假設計算120以内的質數。可以把2、3、5、7先列出來，然後從6開始往後，每次加6得一偶數（12、18、24…）,然後計算該偶數的相鄰奇數是否是質數，計算方法是，首先将個位為5（比如25）的奇數直接pass，在49之前隻需計算能否被3整除，即11、13（12的相鄰奇數）、17、19（18的相鄰奇數）、23（24的相鄰奇數，pass掉25）、29、31（30的相鄰奇數）、37（36的相鄰奇數pass掉35）、41、43（42的相鄰奇數）、47（48的相鄰奇數）隻需計算能否被3整除；在48之後121之前的6的倍數的相鄰奇數隻需計算能否被3、7整除（比如113=114-1隻需計算能否被3、7整除），3、7都不能整除就是質數。（延伸：121=11*11至168=13*13-1則隻需要計算3、7、11……）。

質數的定義：大于1且隻能被1和自身整除的自然數（如：2、3、5、7、11等）。

合數的定義：大于1且不是質數的自然數（如：4,6,8,9,10等）。

簡單地根據質數的定義，要判斷一個數N是否是質數，需要證明2至N-1的自然數都不能整除N，然而事實上很多自然數是可以直接排除質數之外的，比如一個偶數，很明顯能被2整除，又比如位數為5的奇數，很明顯能被5整除，也無需計算。

本文将介紹質數的快速計算方法。比如，如何快速計算出自然數M（M可以足夠大）以内的質數；又比如，在大質數的計算中（通常是用計算機編程計算），如何快速計算一個大數是否是質數。

一、減少需要計算的數

由于除2以外的所有偶數均可以排除，也就是說，除2之外的所有偶數都是合數，無需計算；需要計算的奇數可以定義為：2n 1（或2n-1）,n為自然數；或4n 1及4n 3（可以用4n-1代替）；或6n 1,6n 3，6n 5（可以用6n-1替代）;或8n 1,8n 3，8n 5（8n-3），8n 7（8n-1）……

2n 1方式需要對所有奇數進行計算，未達到減少計算數的目的。

4n 1及4n-1方式也不能減少計算數，因為4*2 1及4*4-1都是合數，而4*2-1和4*4 1都是質數，無法直接減少計算數，也未達到減少計算數的目的。

8n方式可以用8n1及8n3也無法減少計算數（8*1 1,8*2-1,8*33都是合數，所以必須全部運算），也未達到減少計算數的目的。

對于6n1及6n 3方式而言，由于6n 3能被3整除，是無需計算就能排除是質數的，所以用6n1及6n 3方式計算隻需要計算6n1，減少了6n 3的判斷。比如說：計算100以内的質數，2、3以上可以隻計算6*1-1（5）、6*1 1（7），6*2-1（11）、6*2 1（13）,6*3-1（17）、6*3 1（19）……，而9（6*1 3）、15（6*2 3）、21……等奇數是無需計算的，這樣就減少了需要計算的數了（準确地說，每3個奇數可以減少1個計算數）。

如果感興趣，可以從8往後再看看，10n…方式每5個奇數可以減少1個計算數；12n方式每6個奇數可以減少2個計算數，但表達式較6n方式麻煩，且實質上參與運算的數是一樣的；14n方式每7個奇數可以減少1個計算數……。

二、減少計算量

如上節述，2、3以外，可以用計算6n1是否是質數（口算就是從6開始，計算6的倍數的兩個相鄰數（6計算5、7,12計算11、13；18計算17、19,24計算23、25……）是否為質數。

對于每一個需要計算的數，可以用以下方法減少計算量：

對于一個數N（N可以任意大），N的算術平方根的整數部分為x，如果N不能被小于或等于x的任意質數整除，則N為質數（換言之：計算N是否為質數可以隻計算小于或等于x的質數能否整除N）。

能用該算法減少計算量的原因：如果N為合數，則N一定能分解成2個以上的質因數，其中最小的一個質因數一定不會大于x。

三、綜合

計算一個自然數M（M可以足夠大）以内的質數，可以2、3、5、7先列出來，然後從6開始，每次加6得一偶數，計算該偶數的相鄰奇數是否是質數，口算方法是，首先将個位為5（比如25）的直接pass，在49之前隻需計算能否被3整除（5已經一眼排除），在48之後的6的倍數的相鄰奇數隻需計算能否被3、7整除（3、7都不能整除就是質數）。（121-168則隻需要計算3、7、11；169至288=17*17-1隻需計算3、7、11、13……）。在計算大奇數是否為質數時，由于不是口算而是用計算機編程計算，就要把5納入運算，可以建一隊列從小到大依次将計算出的質數保存在隊列中，然後對N=6n1的每一個奇數計算，依次計算3、5、7……、x（x為N的算術平方根的整數部分）是否能整除N即可。

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