前言
哥德巴赫猜想是(Goldbach's Conjecture)是數(shù)論中存在最久的未解問題之一浩习，是一個偉大的世界性的數(shù)學(xué)猜想谱秽，其基本思想可以陳述為：
任何一個大于2的偶數(shù)摹迷，都能表示成兩個素?cái)?shù)之和郊供。
如：
4 = 2 + 2
6 = 3 + 3
96= 23 + 73
本文將采用兩種不同的算法來求出給定范圍 n 內(nèi)的哥德巴赫數(shù)字驮审，并對比其時間復(fù)雜度疯淫，得出更優(yōu)算法。
分析
根據(jù)哥德巴赫猜想未斑，我們可以得出如下信息：
- 哥德巴赫數(shù)字是一個大于2的偶數(shù)币绩。
- 哥德巴赫數(shù)字等于兩個素?cái)?shù)相加类浪。
思路A
思路A與之前見過的很多想法一樣，簡單粗暴诉瓦，采用嵌套 for 循環(huán)力细。思路如下：
- for 循環(huán)依次遍歷 [4, n] 范圍內(nèi)的偶數(shù)睬澡。
- 然后，針對每個數(shù)字（c）再次進(jìn)行 for 循環(huán)找出兩個數(shù)字（a,b）之和等于該數(shù)字的數(shù)字眠蚂。（即 c = a + b）
- 判斷 a,b 是否都為素?cái)?shù)煞聪。
- 輸出結(jié)果。
Show the (garbage) code!
實(shí)現(xiàn)A
我們把思路A實(shí)現(xiàn)的程序分成兩個功能模塊：
-
判斷是否為素?cái)?shù)模塊 int isPrime(int i)逝慧，返回 1 即為素?cái)?shù)昔脯。
int isPrime(int i) { int j; if (i <= 1) return 0; if (i == 2) return 1; for (j = 2; j < i; j ++) { number ++; if (i % j == 0) { return 0; }else if(i != j + 1) { continue; }else { return 1; } } } -
主程序模塊：針對 [4, n] 之間的正偶數(shù)進(jìn)行數(shù)值拆分，然后再用isPrime函數(shù)進(jìn)行篩選笛臣，如果k云稚，j都為素?cái)?shù)沈堡，即滿足哥德巴赫猜想静陈，輸出該數(shù)字。
do { printf("please enter a number:"); int number = 0; scanf("%d", &number); int i, j, k; for (int i = 4; i <= number; i += 2) { for (k = 2; k<= i/2; k ++) { j = i - k; if (isPrime(k)) { if (isPrime(j)) { printf("%d=%d+%d\n",i, k, j); } } } } }while (1);
思路B
遞歸算法，也是我業(yè)余時間自己寫的一個鲸拥，遞歸路徑類似魚骨頭拐格，基本思路如下：
- 針對輸入的 n 進(jìn)行拆分（c = a + b 的形式）并遞歸。
- 如果拆分的數(shù)字 a,b 為偶數(shù)刑赶，則可能為符合哥德巴赫猜想禁荒，回到1。
- 如果 c 為偶數(shù)角撞，且 a,b 為素?cái)?shù)呛伴，即滿足哥德巴赫猜想，輸出該數(shù)字谒所。
這里筆者畫了一張抽象的魚骨頭圖热康，幫助讀者理解：
實(shí)現(xiàn)B
思路B實(shí)現(xiàn)的程序主要分成三個功能模塊，為了區(qū)分思路A劣领，判斷素?cái)?shù)的模塊也采用遞歸的形式：
-
判斷是否為素?cái)?shù) int isPrime(int i)姐军，返回 1 即為素?cái)?shù)。
// 判斷偶數(shù) int isEven(int original) { return (original % 2 == 0); } int isPrimeInner(int original, int current) { if (current<=0 || original<=0 || original == 1) return 0; if (original % 2 == 0) { if (original == 2) return 1; return 0; } if (current > (original / 2) + 1) return 1; if (original % current == 0 && current != 1) return 0; return isPrimeInner(original, current + 2); } // 判斷是否為偶數(shù) int isPrime(int original) { return isPrimeInner(original, 1); } -
遞歸模塊
參數(shù)
current: 代表分裂初始值尖淘，參數(shù)flag: 代表是否深入遍歷奕锌，此處用于控制重復(fù)遍歷的情況，如：original=10 時村生，second=8 時惊暴，兩次會都會重復(fù)遍歷 6/4/2，因此加入flag進(jìn)行限制趁桃，只進(jìn)行一次深入遍歷Ａ苫啊！void splitSumInner(int c, int current, int flag) { // 哥德巴赫為大于2的偶數(shù) if (c <= 2) return; // 如果 current 大于 c 的一半卫病，即代表遍歷完畢 if (current >= (c / 2) + 1) return; // 第一次分裂 c 數(shù)值 int a = current; int b = c - current; // 遞歸遍歷并分裂 c 數(shù)值 splitSumInner(c, ++ current, flag); // 判斷能否深入遍歷 if (flag && a > 2 && isEven(a)) { // 深入遍歷 分裂第一個子偶數(shù) splitSum(a, 0); } if (flag && b > 2 && isEven(b)) { // 深入遍歷 分裂第二個子偶數(shù) splitSum(b, 0); } // 如果 c 為偶數(shù)油啤，且 a,b 為素?cái)?shù)，即滿足哥德巴赫猜想蟀苛，輸出該數(shù)字益咬。 if (isEven(c) && isPrime(a) && isPrime(b)) { printf("\n%d=%d+%d\n",c, a, b); } } // original: 待分裂的原始數(shù)值（ps：會自動分裂 小于 original 下的所有數(shù)值） // flag: 1 代表分裂小于 original 下的所有數(shù)值；0 代表分裂當(dāng)前 original 數(shù)值 void splitSum(int original, int flag) { splitSumInner(original, 1, flag); } -
主程序模塊
void goldbachConjecture(int n) { splitSum(n, 1); } int main() { do { printf("please enter a number:"); int number = 0; scanf("%d", &number); goldbachConjecture(number); } while (1); return 0; }
時間復(fù)雜度對比
時間復(fù)雜度說白了就是算法中基本操作的執(zhí)行次數(shù)帜平，更通俗的說法幽告，就是最深層循環(huán)內(nèi)的語句『蹦＃基本操作的重復(fù)執(zhí)行次數(shù)是和算法的執(zhí)行時間成正比的评腺。下面我們來粗略計(jì)算一下上述算法的時間復(fù)雜度帘瞭。
A 算法分析
在程序 A 中淑掌，與下面的代碼相同，采用嵌套三層 for 循環(huán)的方式進(jìn)行遍歷：
```
for (int i = 1; i <= n; i ++) { // 第一層循環(huán)
for (int j = 1; j <= i; j ++) { // 第二層循環(huán)
for (int k = 1; k <= j; k ++) { // 第三層循環(huán)
count ++;
printf("%d*%d*%d\n", i, j, k);
}
}
}
```
下面我們來剖析一下基本操作：
第一層 for 循環(huán)執(zhí)行 n 次蝶念。
第二層 for 循環(huán)以 i 為規(guī)模分別執(zhí)行 1,2,3,4......n-1,n 次抛腕，集一個公差為 1 的等差數(shù)列芋绸，總次數(shù)為 (n+1)*n/2。
-
第三層 for 循環(huán)采用排列組合來計(jì)算担敌，舉個例子摔敛，當(dāng) n = 3 時，有 10 次基本操作全封，我們把執(zhí)行路徑格式定義成 ijk马昙，如下:
111 211 221 222 311 321 322 331 332 333
B 算法分析
結(jié)論
以上時間復(fù)雜度只是筆者通過簡單粗略的分析得出，僅供參考刹悴。通過上述分析行楞，我們發(fā)現(xiàn)算法A與算法B時間復(fù)雜度是一樣的，感興趣的童鞋可以自己計(jì)算上述兩種算法的時間復(fù)雜度土匀。筆者通過測試發(fā)現(xiàn)子房，相同的問題規(guī)模，隨著 n 的增大就轧，算法B的時間復(fù)雜度要遠(yuǎn)小于算法A证杭。如：n = 100 時，算法B遍歷次數(shù)是 6380 次左右妒御，算法A遍歷次數(shù)高達(dá) 15569 次（論算法糟糕的可怕性...）解愤。源碼地址
