輾轉相除法求最大公約數：C語言標準實現

輾轉相除法求最大公約數：C語言標準實現

歐幾里得算法：gcd(M, N) = gcd(N, M % N)，直到餘數為 0，當前除數即為最大公約數。

代碼實現

#include <stdio.h>

int gcd(int M, int N) {
    if (M <= 0 || N <= 0) return 0;  // 參數校驗
    int R;
    while ((R = M % N) > 0) {
        M = N;
        N = R;
    }
    return N;
}

int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    printf("%d\n", gcd(m, n));
    return 0;
}

關鍵點

• 無需預先保證 M >= N：若 M < N，首次循環 R = M，M=N, N=M 自動交換。
• 參數任一 ≤ 0 返回 0，符合題目要求。
• 時間複雜度 O(log min(M,N))，極高效。

測試

gcd(48, 18) → 6
gcd(17, 5)  → 1
gcd(0, 5)   → 0
gcd(-3, 9)  → 0

此為數論基礎算法，廣泛用於分數化簡、模逆計算、RSA 密鑰生成等場景。