欧几里得算法是求两个数的最大公约数的算法,我们首先假设有两个数a和b,其中a是不小于b的数,记a被b除的余数为r,,那么a可以写成这样的形式:
a = b*q + r其中q是整数。
现在假设a和b的一个约数为u,那么a和b都能被u整除,
a = sub = tus和t都是整数。
这样可以得出
r = a - bq = su - (tu)q = (s - tq)u
所以r也能被u整除,一般规律如下
a和b的约数也整除它们的余数r,所以a和b的任一约数同时也是b和r的约数。
反过来可以得出
b和r的约数同时也是a和b的约数。
这是因为对b和r每一个约数v,有
b = kvr = cv
所以a = b*q+r = (k*v)*q + c*v = (k*q + c)*v
。于是
a和b的最大公约数res, 就是b和r的最大公约数。
设b和r的最大公约数为r1, r和r1的最大公约数为r2...
那么res也是r和r1的最大公约数,也是r1和r2……
上面这个规律就是欧几里得算法的数学核心。因为a>b,可以看出余数r(n)会越来越小,最终变成0;当r(n) = 0时,因为任意数和0的最大公约数就是这个数本身,所以r(n-1)和r(n)的最大公约数就是r(n-1), 所以r(n-1)就是a和b的最大公约数。
写成c语言函数是这样的:
1 2 3 4 5 6 7 8 9 | unsigned int Gcd(unsigned int M,unsigned int N){ unsigned int Rem; while(N){ Rem = M % N; M = N; N =Rem; } return Rem; } |
可以发现这里没有要求M>=N;这是因为如果那样,循环会自动交换它们的值。
发现还是写的不通俗...
来源: http://www.cnblogs.com/kirito-c/p/6910912.html