前言：
当前朋友们对“c语言求最大公约数辗转相除法代码”都比较注重，各位老铁们都想要分析一些“c语言求最大公约数辗转相除法代码”的相关知识。那么小编也在网摘上网罗了一些对于“c语言求最大公约数辗转相除法代码””的相关文章，希望我们能喜欢，小伙伴们快快来了解一下吧！求两个数的最大公因数和最小公倍数，是小学五年级的内容，小学教材中，都是采用短除法来计算的。短除法计算最大公因数简单明了，速度快。但是，对于一些比较大的数，如求8251和6105的最大公因数，我们就不太好找出它们公有的因数，用短除法时，就显得力不从心了。
此时，我们可以用到辗转相除法。这种方法是古希腊数学家欧几里德最先提出来的，所以也叫欧几里德算法（Euclidean algorithm），这个算法最早出现在公元前300年古希腊著名数学家欧几里得的《几何原本》》(第VII卷,命题i和ii)中。而在中国则可以追溯至东汉出现的《九章算术》。
辗转相除法的方法是：用较小数去除较大数，再用出现的余数去除除数，再用这个余数去除得到这个余数的除数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的余数为0时的除数就是这两个数的最大公约数。求出最大公因数后，再用短除法去求最小公倍数就比较简单了。
例解：求3869和6497的最大公因数和最小公倍数
6497÷3869=1……2628用较小数除较大数，余数2628
3869÷2628=1……1241 用余数2628去除上一个算式的除数，余数1241
2628÷1241=2……146
1241÷146=8……73
146÷73=2 余数为0，此时的除数73就是3869和6497的最大公因数。再用短除法，可以求出最小公倍数，如下图。
答：3869和6497的最大公因数是73，最小公倍数是89×53×73=344341。
辗转相除法为什么可以求出最大公因数，是基于如下原理：
两个整数的最大公因数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 − 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公因数。辗转相除法还大量运用在计算机程序设计中。
