最大公约数算法

lixiaotao 2019-11-04

欧几里得算法(辗转相除法)

具体思路是:
这条算法基于一个定理:两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。
首先,我们先计算出a除以b的余数c,把问题转化成求出b和c的最大公约数;然后计算出b除以c的余数d,把问题转化成求出c和d的最大公约数;再然后计算出c除以d的余数e,把问题转化成求出d和e的最大公约数……以此类推,逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算,直到两个数可以整除,或者其中一个数减小到1为止。
————————————————
版权声明:本文为CSDN博主「J0han」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/J0Han/article/details/82467335
该版本的代码运行会出现不可知的错误,所以又找了如下链接可运行

https://www.cnblogs.com/tianqizhi/p/8341415.html
最大公约数算法

相关推荐