用辗转相除法求最小公约数

辗转相除法是一种求最大公约数和最小公倍数的方法，我们可以通过不断地用较小的数去除较大的数，直到余数为0，此时较小的数就是最大公约数，最小公倍数可以通过两数之积除以最大公约数得到。以下是用辗转相除法求最小公约数的步骤：

1. 用较大的数除以较小的数，得到余数r和商q。
2. 如果r为0，则较小的数即为最小公约数。
3. 如果r不为0，则用较小的数除以r，得到余数r1和商q1。
4. 如果r1为0，则r即为最小公约数。
5. 如果r1不为0，则继续用r除以r1，得到余数r2和商q2，直到余数为0为止。

例如，求48和60的最小公约数：

60 ÷ 48 = 1 … 12
48 ÷ 12 = 4 … 0

因此，48和60的最小公约数为12。

相关问题

先用辗转相除法求最大公约数，再用最大公约数求最小公倍数python

好的，下面是Python代码：

# 定义函数求最大公约数
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# 定义函数求最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)

# 输入两个数
num1 = int(input("请输入第一个数："))
num2 = int(input("请输入第二个数："))

# 调用函数求最大公约数和最小公倍数，并输出结果
print("{0}和{1}的最大公约数为：{2}".format(num1, num2, gcd(num1, num2)))
print("{0}和{1}的最小公倍数为：{2}".format(num1, num2, lcm(num1, num2)))

执行结果：

请输入第一个数：12
请输入第二个数：18
12和18的最大公约数为：6
12和18的最小公倍数为：36

先用辗转相除法求最大公约数，再用最大公约数求最小公倍数python用while循环

好的，以下是基于 while 循环的 Python 代码：

# 定义函数求最大公约数
def gcd(a, b):
    while b != 0:
        remainder = a % b
        a = b
        b = remainder
    return a

# 定义函数求最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)

# 输入两个数
num1 = int(input("请输入第一个数："))
num2 = int(input("请输入第二个数："))

# 调用函数求最大公约数和最小公倍数，并输出结果
gcd_result = gcd(num1, num2)
lcm_result = lcm(num1, num2)
print("{0}和{1}的最大公约数为：{2}".format(num1, num2, gcd_result))
print("{0}和{1}的最小公倍数为：{2}".format(num1, num2, lcm_result))

这个程序会要求用户输入两个数，然后调用 `gcd` 函数和 `lcm` 函数分别计算最大公约数和最小公倍数，并输出结果。其中 `gcd` 函数使用 while 循环实现辗转相除法，而 `lcm` 函数则利用了最大公约数的性质。