最大公约数，Greatest Common Divisor，简称GCD。最早接触的求最大公约数的方法应该是小学期间 -- 凭感觉取一个公约数作为除数，让需要求最大公约数的数相除，除得的余数再凭感觉取一个公约数作除数，直至余数无公约数。最后将所有除数相乘就是最大公约数。
这里介绍公元前就提出的一种方法 -- 欧几里德法。
欧几里德法又名辗转相除法，由古希腊数学家欧几里德提出。
依赖的数学定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。
假设 a > b, 不用这个条件照样成立，试着想一下
递归形式
gcd(a, b){
if( a % b == 0 ) return b
return gcd(b, a%b)
}
循环形式
while(b!=0){
temp = a%b
a=b
b=temp
}
最大公约数为a
原文链接: https://www.cnblogs.com/bitor/p/12482356.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/334993
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
