1. 更相减损术

可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。
——《九章算术》

int gcd(int a, int b) {
    if (a > b)
        return gcd(a-b, b);
    if (a < b)
        return gcd(b-a, a);
    return a;
}

2. 辗转相除法

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