求两个数的最大公约数:辗转相除法

原文转自:http://blog.csdn.net/dspingk/archive/2010/02/20/5312976.aspx

辗转相除法．

　　当两个数都较大时，采用辗转相除法比较方便．其方法是：

　　以小数除大数，如果能整除，那么小数就是所求的最大公约数．否则就用余数来除刚才的除数；再用这新除法的余数去除刚才的余数．依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数．

　　例如：求4453和5767的最大公约数时，可作如下除法．

　　5767÷4453＝1余1314

　　4453÷1314＝3余511

　　1314÷511＝2余292

　　511÷292＝1余219

　　292÷219＝1余73

　　219÷73＝3

　　于是得知，5767和4453的最大公约数是73．

　　辗转相除法适用比较广，比短除法要好得多，它能保证求出任意两个数的最大公约数．

///<summary>

///辗转相除法:求两个数的最大公约数

///</summary>

///<param name="num1"></param>

///<param name="num2"></param>

///<returns></returns>

privatestaticintGcd(intnum1,intnum2)

{

intgcd=0;

if(num1==num2)

{

gcd = num1;

}

if(num1>num2)

{

inttmp = num1;

num1 = num2;

num2 = tmp;

}

if(num2 % num1 == 0)

{

gcd = num1;

}

else

{

inttmp = num1;

num1 = num2 % num1;

num2 = tmp;

gcd = Gcd(num1, num2);

}

returngcd;

}

P.S: 最小公倍数 = 二数中的大数/最大公约数）*小数