如何判斷一個較大的數是合數（如何快速判斷一個較大正整數是質數還是合數）

2023-04-19 19:38:05 2

如何快速判斷一個較大正整數是質數還是合數？

如果是判斷一個100以內或比較小的正整數是不是質數，我們只需要運用比較熟悉的2，3，5，7，11，13這些質數去除這個數，如果都不能整除，則該數就是質數，如果能夠被其中某個質數整除，則這個數就是合數。但對於一個較大的整數判斷它是合數還是質數，如何快速作出判斷呢？或者說從最小的質數2開始，要判斷到那個質數終止呢？

比如，899是合數還是質數？

我們從2開始經過驗算已經確認它不能被2，3，3，7，11，13，17，19整除了，至此是否就可以下結論它是質數呢？顯然是不行的，再繼續驗算下去，它能被29整除，即899÷29=31，所以899是合數。

顯然，判斷一個數是不是質數，依次從最小的質數2開始依次驗算它否被這些質數整除，但問題是如果前面連續驗算了許多個仍然沒有出現過整除，究竟要驗算到那個質數為止呢？是不是要驗算到這個數本身才能得出為質數的結論？否則要驗算到能否被多大的質數整除才能作出判斷是質數呢？

下面先了解一下質數的一些特徵：

假設所判斷的整數為N，

當N<2×3時，如果N不是2的倍數，則N是質數；

當N<3×5時，如果N不是2或3的倍數，則N是質數；

當N<5×7時，如果N不是2或3或5的倍數，則N是質數；

當N<7×11時，如果N不是2或3或5或7的倍數，則N是質數；

當N<11×13時，如果N不是2或3或5或7或11的倍數，則N是質數；

一般地，當N<a×b(a，b為連續質數，且a<b)時，如果N不是2或3或5，…或a這些連續質數的倍數，則N是質數；

因此，判斷一個較大的整數N是不是質數，其做法是：找到兩個連續的質數a，b(a<b)，使得N最接近於ab，且N<ab，然後一一驗證N是否能被所有小於a的質數整除即可。

顯然，對於較大的整數N，要找到兩個連續的質數a、b，使得N<ab還是有點困難和麻煩的。注意到a<b，而a、b是連續的質數，所以 a^2<N<ab，即a<√N<√ab，

所以可用[√N]（[√N]表示不超過√N的最大整數）替代a。

例如，判斷2011是質數還是合數？

因為[√2011]=44,所以要判斷2011是不是質數，只需要驗證2011能否被小於44的某個質數整除就可以了，完全沒必要驗證到2011.

也就是說，最多只需要判斷2011能否被43，41，37，31，29，23，19，17，13，11，7，5，3，2這些數中的某一個整除即可。

由於2011都不能被這些質數整除，所以2011是質數。