判斷素?cái)?shù)的方法

根據(jù)定義所有素?cái)?shù)都是大于1的自然數(shù)，那么小于等于1的數(shù)都沒有素?cái)?shù)的概念。數(shù)字2只有1和2兩個(gè)因數(shù)，因而必定是素?cái)?shù)，其他數(shù)字x只要判定從2到x-1都無法被它整除，就證明改數(shù)字是素?cái)?shù)。

仔細(xì)思考就會(huì)發(fā)現(xiàn)，其實(shí)數(shù)字x的因數(shù)分成兩大部分，一部分是小于x的平方根，另外一部分大于x的平方根，小于平方根和大于平方根的部分是一一對(duì)應(yīng)的，因而可以只判斷從2到平方根的數(shù)字是否都能被整除即可。

根據(jù)數(shù)論理論可以把數(shù)字分成6個(gè)大部分，6i,6i+1,6i+2,6i+3,6i+4,6i+5，也就是說數(shù)字x%6計(jì)算的值一定是0,1,2,3,4,5這6個(gè)數(shù)字，而6i,6i+2,6i+3,6i+4一定就是合數(shù)，它們都有除了1之外的因數(shù)，只有6i+1和6i+5可能是素?cái)?shù)，因而一旦判定數(shù)字大于等于且6取模結(jié)果為0,2,3,4就可以判定不是素?cái)?shù)。

最后一種篩選法，就是從2開始可以知道2的所有倍數(shù)都是合數(shù)，不是2的倍數(shù)可能是素?cái)?shù)，第一個(gè)不是2的倍數(shù)的數(shù)一定是素?cái)?shù)，也就是3，接著將3的倍數(shù)全部篩選掉，第一個(gè)不是2的倍數(shù)也不是3的倍數(shù)的數(shù)一定是素?cái)?shù)也就是5，以此類推，最終篩選出某一范圍內(nèi)的所有素?cái)?shù)，接著查表就能得知數(shù)字是否是素?cái)?shù)

質(zhì)數(shù)又稱素?cái)?shù)。指在一個(gè)大于1的自然數(shù)中，除了1和此整數(shù)自身外，沒法被其他自然數(shù)整除的數(shù)。換句話說，只有兩個(gè)正因數(shù)（1和自己）的自然數(shù)即為素?cái)?shù)。比1大但不是素?cái)?shù)的數(shù)稱為合數(shù)。1和0既非素?cái)?shù)也非合數(shù)。合數(shù)是由若干個(gè)質(zhì)數(shù)相乘而得到的。所以，質(zhì)數(shù)是合數(shù)的基礎(chǔ)，沒有質(zhì)數(shù)就沒有合數(shù)。

這也說明了前面所提到的質(zhì)數(shù)在數(shù)論中有著重要地位。歷史上曾將1也包含在質(zhì)數(shù)之內(nèi)，但后來為了算術(shù)基本定理，最終1被數(shù)學(xué)家排除在質(zhì)數(shù)之外，而從高等代數(shù)的角度來看，1是乘法單位元，也不能算在質(zhì)數(shù)之內(nèi)，并且，所有的合數(shù)都可由若干個(gè)質(zhì)數(shù)相乘而得到。