这次给大家带来Python实现求解最大公约数的方法，Python实现求解最大公约数的注意事项有哪些，下面就是实战案例，一起来看一下。

先从网上摘录一段算法的描述如下：

更相减损法：也叫 更相减损术，是出自《 九章算术》的一种求最大公约数的算法，它原本是为 约分而设计的，但它适用于任何需要求最大公约数的场合。

《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”

翻译成现代语言如下：

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

看完上面的描述，我的第一反应是这个描述是不是有问题？从普适性来说的话，应该是有问题的。举例来说，如果我求解4和4的最大公约数，可半者半之之后，结果肯定错了！后面的算法也不能够进行！

不管怎么说，先实现一下上面的算法描述：

# -*- coding:utf-8 -*-#! python2def MaxCommpisor(m,n):  # even process  while m % 2 == 0 and n % 2 == 0:    m = m / 2    n = n / 2  # exchange order when needed  if m  n:      m = diff    else:      m = n      n = diff  return nprint(MaxCommpisor(55,120))print(MaxCommpisor(55,77))print(MaxCommpisor(32,64))print(MaxCommpisor(16,128))

运行结果：

不用说，上面程序执行错误百出。那么该如何更正呢？

首先，除的2最终都应该再算回去！这样，程序修改如下：

def MaxCommpisor(m,n):  com_factor = 1  if m == n:    return n  else:    # process for even number    while m % 2 == 0 and n % 2 == 0:      m = int(m / 2)      n = int(n / 2)      com_factor *= 2    if m <p style="text-align: left;">通过修改，上面程序执行结果如下</p><p style="text-align: left;"><img src="https://img.php.cn/upload/article/000/061/021/855c5db90343f8003754ae8299bd083c-1.png" alt=""></p><p   style="max-width:90%">虽说这段程序写出来看着有点怪怪的，但是总体的算法还是实现了。与辗转相除等算法相比，这个在<a href="http://www.php.cn/code/6276.html" target="_blank">循环</a>的层级上有一定的概率会减小。特别是最后的两组测试数字对儿，这种情况下的效果要好一些。但是，总体上的算法的效率，现在我还不能够给个准确的衡量。</p><p style="text-align: left;"><span style="color: #800000"></span></p><p>相信看了本文案例你已经掌握了方法，更多精彩请关注本站其它相关文章！</p><p>推荐阅读：</p><p><a href="http://www.php.cn/&lt;a%20style='color:#f60;%20text-decoration:underline;'%20href=" https: target="_blank">python</a>-tutorials-391946.html" target="_blank"&gt;Pycharm的使用技巧总结<br></p><p><a href="http://www.php.cn/python-tutorials-391935.html" target="_blank">python如何取得二维数组局部峰值</a><br></p>