GCD 程式

這篇筆記記錄了 GCD（最大公約數）的 C 語言程式。

什麼是 GCD？

資訊

GCD（Greatest Common Divisor），中文稱為最大公約數，是指兩個或多個整數共有的約數中最大的一個。

例如，24 和 36 的公約數有 1、2、3、4、6、12，其中最大的公約數是 12。

歐幾里得演算法 (Euclidean Algorithm)

計算 GCD 最常見且有效的方法是歐幾里得演算法。其原理基於以下定理：

$$ \gcd(a, b) = \gcd(b, a \bmod b) $$

當 $b = 0$ 時，$\gcd(a, 0) = a$。

C 語言程式碼實現

遞迴版本：

// gcd.c
int gcd(int a, int b){
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

非遞迴版本：

// gcd_iterative.c
int gcd_iterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

測試程式

#include <stdio.h>

// 遞迴版本的 GCD 函數
int gcd(int a, int b){
    return !b ? a : gcd(b, a % b);
}

// 非遞迴版本的 GCD 函數
int gcd_iterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}


int main(void){
    printf("GCD(24, 36) = %d
", gcd(24, 36)); // 輸出 12
    printf("GCD_iterative(24, 36) = %d
", gcd_iterative(24, 36)); // 輸出 12
    printf("GCD(48, 18) = %d
", gcd(48, 18)); // 輸出 6
    printf("GCD_iterative(48, 18) = %d
", gcd_iterative(48, 18)); // 輸出 6
    return 0;
}

總結

GCD 是數論中的一個基本概念，歐幾里得演算法提供了一種高效的計算方法。無論是遞迴還是非遞迴實現，其核心思想都是利用模運算將問題規模不斷縮小，直到其中一個數變為零。