更相減損術(shù)

《九章算術(shù)》云：“可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也。以等數(shù)約之。”
即：將較大數(shù)減去較小數(shù)，將所得的差與較小數(shù)進行同樣操作，直到減數(shù)與差相等，此數(shù)即為最大公因數(shù)。

• 遞歸

int gcd(int a, int b) {
    if (a == b)
        return a;
    if (a > b)
        return gcd(a - b, b);
    return gcd(b, a); // 若 a < b, 則交換 a b, 直接進入下一層遞歸
}

• 循環(huán)

int gcd(int a, int b) {
    while (a != b) {
        if (a > b) { // 必需條件: a > b
            a = a - b;
        } else {  // 若 a < b, 則交換 a b
            // 不依賴第三個變量的交換
            a = a - b;
            b = a + b;
            a = b - a;
        }
    }
    return a;
}

輾轉(zhuǎn)相除法

將較大數(shù)除以較小數(shù)，將余數(shù)和較小數(shù)進行同樣操作，直到余數(shù)為零，除數(shù)即為最大公因數(shù)。

• 遞歸

int gcd(int a, int b) {
    if (b == 0)
        return a;
    if (a > b)
        return gcd(b, a % b);
    return gcd(a, b % a);
}

• 循環(huán)

int gcd(int a, int b) {
    int t;
    while (b != 0) {
        if (a > b) { // 必需條件: a > b
            t = a;
            a = b;
            b = t % b;
        } else { // 若 a < b, 則交換 a b
            // 不依賴第三個變量的交換
            a = a - b;
            b = a + b;
            a = b - a;
        }
    }
    return a;
}