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

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

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

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

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

質數(shù)的判斷方法

1）直觀判斷法

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

defisPrime(num):

foriinrange(num):

forjinrange(2,num):

ifi%j==0:break

else:returnTrue

2）直觀判斷法改進

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

frommathimportsqrt

defisPrime(num):

foriinrange(num):

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

ifi%j==0:

break

else:returnTrue

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

首先看一個關于質數(shù)分布的規(guī)律：大于等于5的質數(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ù)兩側，即6x兩側的數(shù)為6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它們一定不是素數(shù)，再除去6x本身，顯然，素數(shù)要出現(xiàn)只可能出現(xiàn)在6x的相鄰兩側。這里要注意的一點是，在6的倍數(shù)相鄰兩側并不是一定就是質數(shù)。