怎样用欧几里得算法算125和71的最小公倍数

设为a,b,
先求出最大公约数gcd(a,b)  再用  lcm(a,b)= a*b/ gcd(a,b); 


 
最大公约数用这个递归算法


int gcd(int a,int b)
{
    if(b==0)  return a; 
    if(a<b) { return gcd(b,a); } 
    return gcd(b,a%b); 
}
对应过程 
gcd(125,71) =  gcd(71,125%71) = gcd(71,54) =gcd(54,71%54) = gcd(54,17) 
=gcd(17,54%17)= gcd(17,3) =gcd(3,17%3) =gcd(3,2) =gcd(2,3%2) = gcd(2,1) = gcd(1,2%1) =gcd(1,0)


所以最大公约数gcd(125,71)= 1;   最小公倍数  lcm=125*71=8875