C 語言輾轉相除法求最大公約數：循環邏輯錯誤修正

問題代碼分析

用戶截圖代碼核心邏輯：

int a, b, c;
scanf("%d %d", &a, &b);
c = a % b;
while (c != 0) {
    a = b;
    b = c;
    // 缺少：c = a % b;  // 關鍵：取模運算必須在循環內更新！
}
printf("%d", b);

錯誤原因

取模運算 c = a % b 僅在循環前執行了一次，循環體內未更新 c。導致：

• 若初始 c != 0，條件永遠為真 → 死循環
• 程序「無結果輸出」實際是卡在死循環中

正確算法邏輯（歐幾里得算法）

int gcd(int a, int b) {
    int c;
    while (b != 0) {        // 以除數為零為終止條件
        c = a % b;          // 關鍵：每輪循環必須重新計算餘數
        a = b;
        b = c;
    }
    return a;               // 最後非零除數即為最大公約數
}

完整可運行程序

#include <stdio.h>

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int a, b;
    printf("輸入兩個正整數: ");
    if (scanf("%d %d", &a, &b) != 2) return 1;
    if (a <= 0 || b <= 0) {
        printf("請輸入正整數\n");
        return 1;
    }
    printf("最大公約數: %d\n", gcd(a, b));
    return 0;
}

遞歸版本（更簡潔）

int gcd_recursive(int a, int b) {
    return b == 0 ? a : gcd_recursive(b, a % b);
}

關鍵點總結

• 循環不變量：gcd(a, b) == gcd(b, a % b)
• 終止條件：除數 b == 0，此時被除數 a 即為結果
• 循環體必須更新餘數：r = a % b; a = b; b = r; 三步缺一不可
• 邊界處理：輸入為 0、負數時的行為需按需定義

總結

「運行無結果」實為死循環。將取模運算移入循環內，以除數為零為終止條件，即可正確實現輾轉相除法。