怎么使用python辗转相除法求最大公约数和最小公倍数

本文小编为大家详细介绍“怎么使用python辗转相除法求最大公约数和最小公倍数”，内容详细，步骤清晰，细节处理妥当，希望这篇“怎么使用python辗转相除法求最大公约数和最小公倍数”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。

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

辗转相除法数学原理

辗转相除法也称欧几里得算法，是用来求两个正整数的最大公约数的算法。接下来我们用实例来解释一下。假如我们需要求12和21的最大公约数，用辗转相除法是这样实现的：

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

至此，得到21与12的最大公约数为3（注意：这里的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)

结果截图

读到这里，这篇“怎么使用python辗转相除法求最大公约数和最小公倍数”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注亿速云行业资讯频道。