質(zhì)數(shù)是什么意思 有哪些判斷方法

質(zhì)數(shù)(primenumber)又稱素?cái)?shù)，有無(wú)限個(gè)。一個(gè)大于1的自然數(shù)，除了1和它本身外，不能被其他自然數(shù)整除，換句話說(shuō)就是該數(shù)除了1和它本身以外不再有其他的因數(shù);否則稱為合數(shù)。根據(jù)算術(shù)基本定理，每一個(gè)比1大的整數(shù)，要么本身是一個(gè)質(zhì)數(shù)，要么可以寫成一系列質(zhì)數(shù)的乘積。

質(zhì)數(shù)是什么意思?

質(zhì)數(shù)(primenumber)又稱素?cái)?shù)，有無(wú)限個(gè)。一個(gè)大于1的自然數(shù)，除了1和它本身外，不能被其他自然數(shù)整除，換句話說(shuō)就是該數(shù)除了1和它本身以外不再有其他的因數(shù);否則稱為合數(shù)。

根據(jù)算術(shù)基本定理，每一個(gè)比1大的整數(shù)，要么本身是一個(gè)質(zhì)數(shù)，要么可以寫成一系列質(zhì)數(shù)的乘積;而且如果不考慮這些質(zhì)數(shù)在乘積中的順序，那么寫出來(lái)的形式是唯一的。最小的質(zhì)數(shù)是2。

質(zhì)數(shù)的判斷方法

1）直觀判斷法

最直觀的方法，根據(jù)定義，因?yàn)橘|(zhì)數(shù)除了1和本身之外沒(méi)有其他約數(shù)，所以判斷n是否為質(zhì)數(shù)，根據(jù)定義直接判斷從2到n-1是否存在n的約數(shù)即可。

defisPrime(num):

foriinrange(num):

forjinrange(2,num):

ifi%j==0:break

else:returnTrue

2）直觀判斷法改進(jìn)

上述判斷方法，明顯存在效率極低的問(wèn)題。對(duì)于每個(gè)數(shù)n，其實(shí)并不需要從2判斷到n-1，我們知道，一個(gè)數(shù)若可以進(jìn)行因數(shù)分解，那么分解時(shí)得到的兩個(gè)數(shù)一定是一個(gè)小于等于sqrt(n)，一個(gè)大于等于sqrt(n)，據(jù)此，上述代碼中并不需要遍歷到n-1，遍歷到sqrt(n)即可，因?yàn)槿魋qrt(n)左側(cè)找不到約數(shù)，那么右側(cè)也一定找不到約數(shù)。

frommathimportsqrt

defisPrime(num):

foriinrange(num):

forjinrange(2,int(sqrt(num))):

ifi%j==0:

break

else:returnTrue

3）質(zhì)數(shù)規(guī)律判斷法

首先看一個(gè)關(guān)于質(zhì)數(shù)分布的規(guī)律：大于等于5的質(zhì)數(shù)一定和6的倍數(shù)相鄰。例如5和7，11和13,17和19等等；

證明：令x≥1，將大于等于5的自然數(shù)表示如下：

······6x-2，6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6x+6，6x+7······

也就是

······2(3x-1)，6x-1，6x，6x+1，2(3x+1)，3(2x+1)，2(3x+2)，6x+5，6(x+1)，6(x+1)+1······

可以看到，不在6的倍數(shù)兩側(cè)，即6x兩側(cè)的數(shù)為6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它們一定不是素?cái)?shù)，再除去6x本身，顯然，素?cái)?shù)要出現(xiàn)只可能出現(xiàn)在6x的相鄰兩側(cè)。這里要注意的一點(diǎn)是，在6的倍數(shù)相鄰兩側(cè)并不是一定就是質(zhì)數(shù)。