1. 素數判定問題

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

2. 原始算法

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

3. 改進算法

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

4. 篩選算法

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

(1) 怎樣快速得到素數表？（采用篩選方法）
(2) 怎樣減少素數表的大??？（采用位圖數據結構）

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

<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
為了減少內存使用率，算法使用了位圖數據結構，關于位圖，可參考：//www.49028c.com/article/54439.htm

5. 優化的篩選算法

(1) 存儲方式優化

仍然采用位圖方式存儲，只不過是位圖中只存儲奇數，這樣一下子節省了一半空間（需要的空間僅為4G/(32*2)=64MB）
存儲空間優化后，算法效率也會提升很多，如：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),結束
即：i=s, 把下標為s(2*t+1)+3t,其中，t=1,2,3，…中所有的的is_primer置為false

(2) 優化刪選算法

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

6. 總結

至今為止，沒有任何人發現素數的分布規律，也沒有人能用一個公式計算出所有的素數。關于素數的很多的有趣的性質或者科學家的努力，如：

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

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

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

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

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