什么叫做辗转相除法

2022-12-24 14:03:23 第一文档网 [ 字体：小中大 ] [

阅读： ] [

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。下载word有问题请添加QQ：admin处理，感谢您的支持与谅解。

【#第一文档网# 导语】以下是®第一文档网的小编为您整理的《什么叫做辗转相除法》，欢迎阅读！
辗转相除法,叫做,什么

什么叫做辗转相除法？

辗转相除法，又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：

用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。示例：

123456 和 7890 的最大公因数是 6，这可由下列步骤（其中，“a mod b”是指取 a ÷ b 的余数）看出：

另一种求两数的最大公约数的方法是更相减损法。

扩展资料：

更相减损法与辗转相除法：

1、两者都是求最大公因数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。

2、从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。

更相损减法在两数相差较大时，时间复杂度容易退化成O(N)，而辗转相除法可以稳定在O(logN)。但辗转相除法需要试商，这就使得在某些情况下，使用更相损减法比使用辗转相除法更加简单。而stein算法便由此出现。

本文来源：https://www.dywdw.cn/e0c84be2a65177232f60ddccda38376bae1fe03e.html