有人做過(guò)這樣的驗(yàn)算：1^2+1+41=43,2^2+2+41=47,3^2+3+41=53……于是就可以有這樣一個(gè)公式：設(shè)一正數(shù)為n，則n^2+n+41的值一定是一個(gè)質(zhì)數(shù)。這個(gè)式子一直到n=39時(shí)，都是成立的。但n=40時(shí)，其式子就不成立了，因?yàn)?0^2+40+41=1681=41*41。
研究發(fā)現(xiàn)質(zhì)數(shù)除2以外都是奇數(shù)，而奇數(shù)除了【奇數(shù)*奇數(shù)】(或再加“*奇數(shù)”）都是質(zhì)數(shù)。那么用計(jì)算機(jī)先把【奇數(shù)*奇數(shù)】(或再加“*奇數(shù)”）（比如9，15，21，25，27，33，35，39……）都求出來(lái)，再找奇數(shù)中上面沒(méi)提到的那些數(shù)，那些數(shù)就是素?cái)?shù)。
有近似公式： x 以內(nèi)質(zhì)數(shù)個(gè)數(shù)約等于 x / ln(x) .ln是自然對(duì)數(shù)的意思。準(zhǔn)確的質(zhì)數(shù)公式尚未給出。10 以內(nèi)共 4 個(gè)質(zhì)數(shù)。100 以內(nèi)共 25 個(gè)質(zhì)數(shù)。
古老的篩法：可快速求出100000000以內(nèi)的所有素?cái)?shù)。篩法，是求不超過(guò)自然數(shù)N（N＞1）的所有質(zhì)數(shù)的一種方法。據(jù)說(shuō)是古希臘的埃拉托斯特尼（Eratosthenes，約公元前274～194年）發(fā)明的，又稱埃拉托斯特尼篩子。具體做法是：先把N個(gè)自然數(shù)按次序排列起來(lái)。1不是質(zhì)數(shù)，也不是合數(shù)，要?jiǎng)澣ァ５诙€(gè)數(shù)2是質(zhì)數(shù)留下來(lái)，而把2后面所有能被2整除的數(shù)都劃去。2后面第一個(gè)沒(méi)劃去的數(shù)是3，把3留下，再把3后面所有能被3整除的數(shù)都劃去。3后面第一個(gè)沒(méi)劃去的數(shù)是5，把5留下，再把5后面所有能被5整除的數(shù)都劃去。這樣一直做下去，就會(huì)把不超過(guò)N的全部合數(shù)都篩掉，留下的就是不超過(guò)N的全部質(zhì)數(shù)。
素?cái)?shù)判斷法：考慮到這么一個(gè)現(xiàn)實(shí)：任何一個(gè)合數(shù)都可以表現(xiàn)為適當(dāng)個(gè)素?cái)?shù)的乘積的形式，所以我們只用素?cái)?shù)去除要判斷的數(shù)即可，比如要判斷100以內(nèi)的素?cái)?shù)，只用10以內(nèi)的2，3，5，7就夠了，10000以內(nèi)的數(shù)用100以內(nèi)的素?cái)?shù)判斷足以。
Rabin-Miller算法：首先我們必須保證n 是個(gè)奇數(shù)，那么我們就可以把n 表示為 n = (2^r)*s+1,注意s 也必須是一個(gè)奇數(shù)。然后我們就要選擇一個(gè)隨機(jī)的整數(shù)a (1<=a<=n-1)，接下來(lái)我們就是要判斷 a^s=1 (mod n) 或a^((2^j)*s)= -1（mod n）(0<=j如果任意一式成立，我們就說(shuō)n通過(guò)了測(cè)試，但是有可能不是素?cái)?shù)也能通過(guò)測(cè)試。所以我們通常要做多次這樣的測(cè)試，以確保我們得到的是一個(gè)素?cái)?shù)。（DDS的標(biāo)準(zhǔn)是要經(jīng)過(guò)50次測(cè)試）采用Rabin- Miller算法進(jìn)行驗(yàn)算的方法：
0、對(duì)于需要驗(yàn)證的數(shù)n，先計(jì)算出m、j，使得n=1+m*2^j，其中m是正奇數(shù)，j是非負(fù)整數(shù)
1、隨機(jī)取一個(gè)b，2<=b<n
2、計(jì)算v=b^m mod n
3、如果v==1，通過(guò)測(cè)試，返回
4、令i=1
5、如果v=n-1，通過(guò)測(cè)試，返回
6、如果i==j，非素?cái)?shù)，結(jié)束
7、v=v^2 mod n，i=i+1
8、循環(huán)到5