欧几里得算法求最大公约数(gcd)

关于欧几里得算法求最大公约数算法,

代码如下:

int gcd( int a , int b )

{

if( b == 0 ) return a ;

else gcd( b , a % b  ) ;

 }

证明:

对于a,b,有a = kb + r  (a , k , b , r 均为整数),其中r = a mod b .

令d为a和b的一个公约数,则d|a,d|b(即a、b都被d整除),

那么 r =a - kb ,两边同时除以d

得 r/d = a/d - kb/d = m (m为整数,因为r也被d整除)

所以可知

a,b 的公约数和 b , a mod b  公约数一样,所以他们最大公约数也一样。

即就是 gcd ( a , b ) = gcd ( b , r )

当r=0时,b显然是(b,r)的最大公约数,也即就是a,b的最大公约数,

上一篇:转 这种方法可以免去自己计算大文件md5 的麻烦


下一篇:Linux shell 通配符 / glob 模式