Python实现辗转相除法求最大公约数与最小公倍数

清欢

发布时间：2026-10-15| 4人浏览过

原创

本文详细介绍利用Python实现辗转相除法（欧几里得算法）求解两个正整数的最大公约数和最小公倍数。内容涵盖算法数学原理、迭代与递归两种代码实现方式，以及交互式输入输出的完整示例，帮助开发者快速掌握相关编程技巧。

Python辗转相除法求最大公约数和最小公倍数

辗转相除法数学原理

辗转相除法，也被称为欧几里得算法，是一种用于计算两个正整数最大公约数的经典算法。为了便于理解，我们通过具体实例进行说明。例如，计算12和21的最大公约数，其计算过程如下：

21 / 12 = 1 （余 9）
12 / 9 = 1（余 3）
9 / 3 = 3 （余 0）

通过上述步骤，我们得出21与12的最大公约数为3。需要注意的是，这里的3来源于第二个式子中的余数，而非最后一个式子的商。得到最大公约数后，计算最小公倍数的公式为：两数之积除以最大公约数，即（21 * 12）/ 3 = 84。

Python代码实现

下面我们将使用Python代码来实现上述计算逻辑：

题目要求：输入两个正整数，并计算它们的最大公约数和最小公倍数。

def func(m,n):
    a = m
    b = n
    # 默认m>n，若不是，则交换
    if m < n:
        m,n = n,m
    while n != 0:
        # 对m除n取余
        r = m % n
        m = n
        n = r
    return m,(a*b)/m

print("正整数m与n的最大公约数与最小公倍数分别为：",func(12,21))

正整数m与n的最大公约数与最小公倍数分别为： (3, 84.0)

使用递归方式实现

def rec(m,n):
    # 默认m>n，若不是，则交换
    if m < n:
        m,n = n,m
    # 终止条件    
    if n == 0:
        return m,(a*b)/m
    # 递归部分
    return rec(n,m%n)

a = 12
b = 21

print("正整数m与n的最大公约数与最小公倍数分别为：",rec(12,21))

正整数m与n的最大公约数与最小公倍数分别为： (3, 84.0)

Python3 20.辗转相除法

算法分析

1. 算法定义：指在有限步骤内解决数学问题的程序。它是为了解决特定工作或问题而设计的一系列有限数量的机械性或重复性指令与计算步骤。

2. 最大公约数：指能同时整除两个整数的最大整数。

3. 计算步骤：用两个数中较大的整数除以较小的整数，得到商和余数。

源代码

# coding:gbk
Num_1 = int(input("请输入一个整数： "))
Num_2 = int(input("请输入一个整数： "))

if Num_1 < Num_2:
	Tmp_Num = Num_1       # 是交换而不是赋值
	Num_1 = Num_2
	Num_2 = Tmp_Num

while Num_2 != 0:
	Tmp_Num = Num_1 % Num_2
	Num_1 = Num_2
	Num_2 = Tmp_Num

print('输出这两个整数的最大公约数：', Num_1)