1. 素數(shù)判定問題

素數(shù)判定問題是一個非常常見的問題，本文介紹了常用的幾種判定方法。

2. 原始算法

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

3. 改進算法

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

4. 篩選算法

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

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

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

<1> 定義is_primer[i] = true;
<2> 從2開始，依次遍歷整個is_primer(直到sqrt(N))，如果is_primer[i]=true,則is_primer[n*i]=false
如1,2,3,4,5,6,7,8,9,10，則
從2開始遍歷：
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) 存儲方式優(yōu)化

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

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

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

6. 總結(jié)

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

(1) 高斯猜測，n以內(nèi)的素數(shù)個數(shù)大約與n/ln(n)相當，或者說，當n很大時，兩者數(shù)量級相同。這就是著名的素數(shù)定理。

(2) 十七世紀費馬猜測，2的2^n次方+1，n=0，1，2…時是素數(shù)，這樣的數(shù)叫費馬素數(shù)，可惜當n=5時，2^32+1就不是素數(shù)，至今也沒有找到第六個費馬素數(shù)。

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

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

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