求最大公约数的几种方法

最近在辅导我儿子学习 Python 编程,很多算法的步骤中都会涉及到求最大公约数的问题,因此我将不同的算法实现记录在这里。

枚举法

枚举法是最容易理解的方式,利用公约数的定义,从两个数中较小的一个数开始,不断比较该数与两个数相除的余数是否都为零。代码实现如下:

1
2
3
4
5
6
def enumFromMin(num1, num2):
if num1 < num2:
num1, num2 = num2, num1
for i in range(num2 - 1, 0, -1):
if num1 % i == 0 and num2 % i == 0:
return i

枚举法虽然理解起来简单,但时间复杂度比较高,比如我们求 27和21 的最大公约数,用枚举法需要18步(循环18次),而且每次需要进行两个数的取余操作,如果两个数都比较大的时候,会非常耗时,因此在实际工作中要尽量避免使用。

辗转相除取余法

算法描述如下:

已知两个整数 num1 和 num2, 求最大公约数:

  1. num1 除以 num2, 取余数为 ok
  2. 若 ok 等于零,则 ok 即为 num1 和 num2 的最大公约数
  3. 若 ok 不等于零,则 num1 = num2, num2 = ok, 在回到第一步开始

对应的代码如下:

1
2
3
4
5
6
def loopDivision(num1, num2):
ok = num1 % num2
while ok != 0:
num1, num2 = num2, ok
ok = num1 % num2
return num2

同样求27和21 的最大公约数,只需要3步即可完成,只需要三次取余计算。

循环相减法

算法描述如下:

已知两个整数 num1 和 num2, 求最大公约数:

  1. 如果 num1 > num2, 则 num1 = num1 - num2
  2. 如果 num1 < num2, 则 num2 = num2 = num1
  3. 如果 num1 等于 num2, 则找到了最大公约数(num1 或 num2 皆可,因为二者相等)
  4. 如果 num1 不等于 num2, 则回到第一步执行

代码如下:

1
2
3
4
5
6
7
def loopSubstraction(num1, num2):
while num1 != num2:
if num1 > num2:
num1 = num1 - num2
else:
num2 = num2 - num1
return num1

同样求27和21 的最大公约数,只需要5步即可完成。

本文标题:求最大公约数的几种方法

文章作者:梅老师

发布时间:2020年03月28日 - 11:03

最后更新:2020年05月28日 - 16:05

原始链接:https://www.mls-tech.info/python/python-algorithm-max-common-divisor/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。