详解欧几里得算法
浏览数：15 /
时间：2015年06月08日
现有两个整数，a，b。
若a > b，则一定有a = kb + q。
可以得到 a除以b，可以得到k余q，即a % b = q。
假设d同时是a和b的最大公约数，则a能够被d整除，b也能被d整除，q = a - kb 所以q也能够被d整除，所以d是b和q的公约数。
所以a和b的公约数d同时也是b与q(a % b)的公约数。
令a2 = b， b2 = q， 求余，则q2 = b % q。
以此类推，不断地求余，最后bn = 一个数, qn = 0
此时，这bn和与一开始的a和b同时有最大公约数d。
而bn的最大公约数为bn，所以bn为a和b的最大公约数。
代码如下:
迭代版
int gcd (int a, int b) { while (b != 0) { int temp = a; a = b; b = temp % b; } return a; }
递归版
int gcd (int a, int b) { if (b == 0) { return a; } return gcd (b, a % b); }
代码仅供参考，如果哪里有不足，欢迎各位指教，我一定会进行改进和优化。
如果要转载，请注明出处。
2015.2.9 黑骐
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
