数论-最大公约数与最小公倍数

最大公约数：

int gcd(int a,int b){//Greatest common divisor
    int c;
    while(b){
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}

递归代码：

int _gcd_(int a,int b){
    return b?_gcd_(b,a%b):a;
}

gcb的两个重要结论：

1)            gcd(a,b) =  gcd(b,a %b);

2)            gcd(a,0) =  a.

最小公倍数：

int lcm(int a,int b){//least common multiple
    return a*b/gcd(a,b);
}