Python 中两个数字的 GCD

最大公约数 (GCD) 是一个数学术语，用于找到可以完美整除两个数的最大公因数。GCD 也称为最高公因数 (HCF)。例如，两个数 54 和 24 的 HCF/GCD 是 6。因为 6 是能完全整除 54 和 24 的最大公约数。

使用 gcd() 函数的 GCD

在 Python 中，gcd() 是 math 模块提供的一个内置函数，用于查找两个数​​的最大公约数。

语法

其中 a 和 b 是作为参数传递给 gcd() 函数的两个整数。

让我们创建一个程序，使用 Python math.gcd() 的内置函数来打印两个数的 GCD。

math_fun.py

输出

在上面的示例中，math.gcd() 函数生成两个给定数的 GCD。在 gcd() 函数中，a 和 b 作为参数传递，该函数返回两个整数的最大公约数，这些整数可以被完全整除。

使用递归的 GCD

递归是 Python 中一种耗费内存的函数，它通过自引用表达式调用自身。这意味着该函数将不断调用并重复自身，直到满足定义的条件以返回​​数字的最大公约数。

算法的伪代码

步骤 1：从用户那里获取两个输入 x 和 y。

步骤 2：将输入数字作为参数传递给递归函数。

步骤 3：如果第二个数字等于零 (0)，则返回第一个数字。

步骤 4：否则，它将递归调用该函数，并将第二个数字作为参数，直到得到余数，该余数用第一个数字除以第二个数字。

步骤 5：调用或将 gcd_fun() 分配给一个变量。

步骤 6：显示两个数的 GCD。

步骤 7：退出程序。

让我们通过递归来理解查找两个数​​ GCD 的程序。

gcdRecur.py

输出

使用循环的 GCD

让我们使用循环创建一个程序来查找 Python 中两个数​​的 GCD。

gcdFile.py

输出

如上例所示，我们输入两个值，并将这些数字传递给 GCD_Loop () 函数以返回 GCD。

使用欧几里得算法或欧几里得算法的 GCD

欧几里得算法是查找两个数​​最大公约数的有效方法。它是最古老的算法，它将较大的数除以较小的数并取余数。再次，它用余数除以较小的数，该算法持续除以该数，直到余数为 0。

例如，假设我们要计算两个数 60 和 48 的 HCF。然后我们将 60 除以 48；它返回余数 12。现在我们再次将 24 除以 12，然后返回余数 0。所以，通过这种方式，我们得到 HCF 是 12。

欧几里得算法的伪代码

步骤 1：有两个整数，例如 a 和 b。

步骤 2：如果 a = 0，则 GCD(a, b) 为 b。

步骤 3：如果 b = 0，则 GCD(a, b) 为 a。

步骤 4：a mod b 找到

步骤 5：假设 a = b 且 b = R

步骤 6：重复步骤 4 和 3，直到 a mod b 等于或大于 0。

步骤 7：GCD = b，然后打印结果。

步骤 8：停止程序。

让我们在 Python 中使用欧几里得算法查找两个数​​的 HCF 或 GCD。

Euclid.py

输出