01-哥德巴赫猜想(Goldbach's Conjecture)--(C語言)

goldbach-partitions-of-the-even.png

前言

哥德巴赫猜想是(Goldbach's Conjecture)是數(shù)論中存在最久的未解問題之一，是一個(gè)偉大的世界性的數(shù)學(xué)猜想，其基本思想可以陳述為：

任何一個(gè)大于2的偶數(shù)，都能表示成兩個(gè)素?cái)?shù)之和。

如：
4 = 2 + 2
6 = 3 + 3
96= 23 + 73

本文將采用兩種不同的算法來求出給定范圍 n 內(nèi)的哥德巴赫數(shù)字，并對比其時(shí)間復(fù)雜度，得出更優(yōu)算法。

分析

根據(jù)哥德巴赫猜想，我們可以得出如下信息：

  1. 哥德巴赫數(shù)字是一個(gè)大于2的偶數(shù)。
  2. 哥德巴赫數(shù)字等于兩個(gè)素?cái)?shù)相加。

思路A

思路A與之前見過的很多想法一樣，簡單粗暴，采用嵌套 for 循環(huán)。思路如下：

  1. for 循環(huán)依次遍歷 [4, n] 范圍內(nèi)的偶數(shù)。
  2. 然后，針對每個(gè)數(shù)字（c）再次進(jìn)行 for 循環(huán)找出兩個(gè)數(shù)字（a,b）之和等于該數(shù)字的數(shù)字。（即 c = a + b）
  3. 判斷 a,b 是否都為素?cái)?shù)。
  4. 輸出結(jié)果。

Show the (garbage) code!

實(shí)現(xiàn)A

我們把思路A實(shí)現(xiàn)的程序分成兩個(gè)功能模塊：

  1. 判斷是否為素?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;
        }
    }
}

  2. 主程序模塊：針對 [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è)余時(shí)間自己寫的一個(gè)，遞歸路徑類似魚骨頭，基本思路如下：

  1. 針對輸入的 n 進(jìn)行拆分（c = a + b 的形式）并遞歸。
  2. 如果拆分的數(shù)字 a,b 為偶數(shù)，則可能為符合哥德巴赫猜想，回到1。
  3. 如果 c 為偶數(shù)，且 a,b 為素?cái)?shù)，即滿足哥德巴赫猜想，輸出該數(shù)字。

這里筆者畫了一張抽象的魚骨頭圖，幫助讀者理解：

goldbach-conjecture-fish.png

實(shí)現(xiàn)B

思路B實(shí)現(xiàn)的程序主要分成三個(gè)功能模塊，為了區(qū)分思路A，判斷素?cái)?shù)的模塊也采用遞歸的形式：

  1. 判斷是否為素?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);
}

  2. 遞歸模塊

    參數(shù) current: 代表分裂初始值，參數(shù) flag: 代表是否深入遍歷，此處用于控制重復(fù)遍歷的情況，如：original=10 時(shí)，second=8 時(shí)，兩次會(huì)都會(huì)重復(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)) {
        // 深入遍歷 分裂第一個(gè)子偶數(shù)
        splitSum(a, 0);
    }

    if (flag && b > 2 && isEven(b)) {
        // 深入遍歷 分裂第二個(gè)子偶數(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：會(huì)自動(dòng)分裂 小于 original 下的所有數(shù)值）
// flag: 1 代表分裂小于 original 下的所有數(shù)值；0 代表分裂當(dāng)前 original 數(shù)值
void splitSum(int original, int flag) {
    splitSumInner(original, 1, flag);
}

  3. 主程序模塊

    
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;
}

時(shí)間復(fù)雜度對比

時(shí)間復(fù)雜度說白了就是算法中基本操作的執(zhí)行次數(shù)，更通俗的說法，就是最深層循環(huán)內(nèi)的語句。基本操作的重復(fù)執(zhí)行次數(shù)是和算法的執(zhí)行時(shí)間成正比的。下面我們來粗略計(jì)算一下上述算法的時(shí)間復(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);
            }
        }
    }

```

下面我們來剖析一下基本操作：

  1. 第一層 for 循環(huán)執(zhí)行 n 次。

  2. 第二層 for 循環(huán)以 i 為規(guī)模分別執(zhí)行 1,2,3,4......n-1,n 次，集一個(gè)公差為 1 的等差數(shù)列，總次數(shù)為 (n+1)*n/2。

  3. 第三層 for 循環(huán)采用排列組合來計(jì)算，舉個(gè)例子，當(dāng) n = 3 時(shí)，有 10 次基本操作，我們把執(zhí)行路徑格式定義成 ijk，如下:

    
111
211  221  222
311  321  322  331  332  333
algorithm-analyze-a.png

B 算法分析

algorithm-analyze-b.png

結(jié)論

以上時(shí)間復(fù)雜度只是筆者通過簡單粗略的分析得出，僅供參考。通過上述分析，我們發(fā)現(xiàn)算法A與算法B時(shí)間復(fù)雜度是一樣的，感興趣的童鞋可以自己計(jì)算上述兩種算法的時(shí)間復(fù)雜度。筆者通過測試發(fā)現(xiàn)，相同的問題規(guī)模，隨著 n 的增大，算法B的時(shí)間復(fù)雜度要遠(yuǎn)小于算法A。如：n = 100 時(shí)，算法B遍歷次數(shù)是 6380 次左右，算法A遍歷次數(shù)高達(dá) 15569 次（論算法糟糕的可怕性...）。源碼地址

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容