質數是什么意思 有哪些判斷方法

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

質數是什么意思?

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

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

質數的判斷方法

1）直觀判斷法

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

defisPrime(num):

foriinrange(num):

forjinrange(2,num):

ifi%j==0:break

else:returnTrue

2）直觀判斷法改進

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

frommathimportsqrt

defisPrime(num):

foriinrange(num):

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

ifi%j==0:

break

else:returnTrue

3）質數規律判斷法

首先看一個關于質數分布的規律：大于等于5的質數一定和6的倍數相鄰。例如5和7，11和13,17和19等等；

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

······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的倍數兩側，即6x兩側的數為6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它們一定不是素數，再除去6x本身，顯然，素數要出現只可能出現在6x的相鄰兩側。這里要注意的一點是，在6的倍數相鄰兩側并不是一定就是質數。