一條學校的 ACM 演練題目，很讓人鬱悶
今天之所以想講關於求質數的演算法，完全跟這條題目有關，看到題目的朋友一定現在已經有了思路了吧，不過下面的講解會讓你很鬱悶，hoho，帶上你的思維，跟著我來
第一，分析題目 排除 10000 以內，就是求一個質數滿足其的值等於兩個質數的平方和就是要滿足
K= A^2 + B^2 這個要求，其中 A，B 是質數，K 當然是要求的質數，那好解法可以這樣求一個質數，然後再求出另一個不同的，為什麼不同，要是相同 K>2 的話，K 肯定不質數了，好然後再平方啊，再來相加，最後再驗證所得的 K 是不質數了，結果出來，說實話，當你等待了 N 秒之後發現結構仍然沒有出來之後的時候你會覺得自己的演算法該優化了，其實我開始是這麼想的，結果。。。
好，說說我的想法 ，講點數學吧
(1) (A + B)^2 = A^2 + 2*AB + B^2 ,"平方和" 與 "和的平方的" 轉換公式
(2) 奇偶公式：兩個偶數之和是偶數，兩個偶數之積是偶數 兩個奇數之和是偶數，兩個奇數之積是奇數 一個奇數和一個偶數之和是奇數，之積是偶數 (3) 哥德巴赫猜想：任意兩個大於 2 素數之和是偶數
第三條很重要，雖然是猜想，但是在計算機科學可以計算的數據大小類是可以證明 的，窮舉法嘛
數學說完，繼續我們的演算法優化，請繼續看下面的分析
K = A^2 + B^2 => K = (A + B)^2 - 2*AB
因為 A + B 是偶數（哥德巴赫猜想），那麼 (A + B)^2 也是偶數，K 是質數，如果 K != 2 那麼 K 肯定是奇數，為什麼？這個我就不解釋了，繼續推導
K 是奇數，(A + B)^2 是偶數，那麼 2*AB 就一定是偶數，2 乘以一個數的話，肯定是 偶數了，偶數加偶數是偶數，但是 K 是質數啊，不偶數啊，為什麼呢？那麼，可以肯 定 A，B 當中肯定有一個數符合特殊情況，比如 1，2
那麼， 如果 A = B = 1 ， K = 2，符合要求 如果 A ，B 當中一個為 1 ， 那麼舉個反例 A = 1 ，B = 3，K=10 不符合 要求，而且，奇數的平方是奇數，那麼這個奇數加 1 肯定是偶數了，偶數還提什麼 素數幹嘛呢 如果 A = B = 2 ，K = 8 ， 不符合 所以，A，B 符合一種情況 A ，B 當中必定有一個數為 2，另一個數為另一個 質數，單獨考慮 1，2 的情況 K=5，符合條件。
綜上，K 的集合 {2 , 5} 加上其他符合一個質數 2 為，另一個為除 1，2 外其它質數，
所以演算法可以優化成
K = 4 + B^2 這回簡單了吧
演算法如下 (演算法描述語言)： 演算法複雜度 O (N), 還可以優化到 O (SQRT (N)) 加上判斷是否是質數的演算法複雜度 結果最壞也就是 O (N^2)
相比那個先求兩個質數，再平方後求，然後再判斷是否是質數的方法來說確實減少 不少消耗
//isPrime () 判斷數是否是素數
int N = 10000
int i;
for i = 3 to sqrt(N)
if isPrime( i^2 + 4)
return(i^2 + 4)
else
i = i + 1