1. 素?cái)?shù)判定問(wèn)題

素?cái)?shù)判定問(wèn)題是一個(gè)非常常見(jiàn)的問(wèn)題，本文介紹了常用的幾種判定方法。

2. 原始算法

素?cái)?shù)的定義是，除了能被1和它本身整除而不能被其他任何數(shù)整除的數(shù)。根據(jù)素?cái)?shù)定義 只需要用2到n-1去除n，如果都除不盡，則n是素?cái)?shù)，否則，只要其中有一個(gè)數(shù)能整除則n不是素?cái)?shù)。

3. 改進(jìn)算法

n不是素?cái)?shù)，則n可表示為a*b，其中2<=a<=b<=n-1,則a，b中必有一個(gè)數(shù)滿足：1<x<=sqrt(n)，因而，只需要用2~sqrt(n)去除n，這樣就得到一個(gè)復(fù)雜度為O(sqrt(n))的算法

4. 篩選算法

更高效地素?cái)?shù)判斷方法應(yīng)該是將素?cái)?shù)預(yù)先保存到一個(gè)素?cái)?shù)表中，當(dāng)判斷一個(gè)數(shù)是否為素?cái)?shù)時(shí)，直接查表即可。這種方法需要解決兩個(gè)問(wèn)題：

(1) 怎樣快速得到素?cái)?shù)表？（采用篩選方法）
(2) 怎樣減少素?cái)?shù)表的大?。浚ú捎梦粓D數(shù)據(jù)結(jié)構(gòu)）

對(duì)于1到n全部整數(shù)，逐個(gè)判斷它們是否是素?cái)?shù)，找出一個(gè)非素?cái)?shù)，就把它挖掉，最后剩下的就是素?cái)?shù)。具體方法是：

<1> 定義is_primer[i] = true;
<2> 從2開(kāi)始，依次遍歷整個(gè)is_primer(直到sqrt(N))，如果is_primer[i]=true,則is_primer[n*i]=false
如1,2,3,4,5,6,7,8,9,10，則
從2開(kāi)始遍歷：
is_primer[2]=true，則is_primer[4]= is_primer[6]= is_primer[8]= is_primer[10]= true
is_primer[3]=true，則is_primer[6]= is_primer[9]= true
為了減少內(nèi)存使用率，算法使用了位圖數(shù)據(jù)結(jié)構(gòu)，關(guān)于位圖，可參考：//www.jb51.net/article/54439.htm

5. 優(yōu)化的篩選算法

(1) 存儲(chǔ)方式優(yōu)化

仍然采用位圖方式存儲(chǔ)，只不過(guò)是位圖中只存儲(chǔ)奇數(shù)，這樣一下子節(jié)省了一半空間（需要的空間僅為4G/(32*2)=64MB）
存儲(chǔ)空間優(yōu)化后，算法效率也會(huì)提升很多，如：1,2，…,30
只需存儲(chǔ)3,5,7,9,11,13,15,17,19,21,23,25,27,29
i=0, is_primer[0] =true, 把下標(biāo)[3][6][9][12]，即9,15,21,27,標(biāo)為false
i=1, s_primer[0] =true,把下標(biāo)為[6][11],即15,25標(biāo)為false
i=2, 2*i+3>sqrt(30),結(jié)束
即：i=s, 把下標(biāo)為s(2*t+1)+3t,其中，t=1,2,3，…中所有的的is_primer置為false

(2) 優(yōu)化刪選算法

a是素?cái)?shù)，則下一個(gè)起點(diǎn)是a*a,把后面的所有的a*a+2*i*a篩掉。即欲求n以內(nèi)的素?cái)?shù)，就先把sqrt(n)內(nèi)的素?cái)?shù)求出來(lái)，用已經(jīng)求得的素?cái)?shù)來(lái)篩出后面的合數(shù)。

6. 總結(jié)

至今為止，沒(méi)有任何人發(fā)現(xiàn)素?cái)?shù)的分布規(guī)律，也沒(méi)有人能用一個(gè)公式計(jì)算出所有的素?cái)?shù)。關(guān)于素?cái)?shù)的很多的有趣的性質(zhì)或者科學(xué)家的努力，如：

(1) 高斯猜測(cè)，n以內(nèi)的素?cái)?shù)個(gè)數(shù)大約與n/ln(n)相當(dāng)，或者說(shuō)，當(dāng)n很大時(shí)，兩者數(shù)量級(jí)相同。這就是著名的素?cái)?shù)定理。

(2) 十七世紀(jì)費(fèi)馬猜測(cè)，2的2^n次方+1，n=0，1，2…時(shí)是素?cái)?shù)，這樣的數(shù)叫費(fèi)馬素?cái)?shù)，可惜當(dāng)n=5時(shí)，2^32+1就不是素?cái)?shù)，至今也沒(méi)有找到第六個(gè)費(fèi)馬素?cái)?shù)。

(3) 18世紀(jì)發(fā)現(xiàn)的最大素?cái)?shù)是2^31-1，19世紀(jì)發(fā)現(xiàn)的最大素?cái)?shù)是2^127-1，20世紀(jì)末人類(lèi)已知的最大素?cái)?shù)是2^859433-1，用十進(jìn)制表示，這是一個(gè)258715位的數(shù)字。

(4) 孿生素?cái)?shù)猜想：差為2的素?cái)?shù)有無(wú)窮多對(duì)。目前知道的最大的孿生素?cái)?shù)是1159142985×2^2304－1和1159142985×2^2304＋1。

(5) 歌德巴赫猜想：大于2的所有偶數(shù)均是兩個(gè)素?cái)?shù)的和，大于5的所有奇數(shù)均是三個(gè)素?cái)?shù)之和。其中第二個(gè)猜想是第一個(gè)的自然推論，因此歌德巴赫猜想又被稱(chēng)為1+1問(wèn)題。我國(guó)數(shù)學(xué)家陳景潤(rùn)證明了1+2，即所有大于2的偶數(shù)都是一個(gè)素?cái)?shù)和只有兩個(gè)素?cái)?shù)因數(shù)的合數(shù)的和。國(guó)際上稱(chēng)為陳氏定理。