python最大公约数和最小公倍数

在Python中，求最大公约数和最小公倍数有几种常用的方法。

方法一：辗转相除法。该方法的具体步骤是，用较小数除较大数，再用出现的余数去除除数，反复进行，直到余数为0。最后的除数即为最大公约数。最小公倍数可以通过两个数的乘积除以最大公约数得到。

方法二：更相减损法。该方法的步骤是，任意给定两个正整数，判断它们是否都是偶数，若是，则用2约简；若不是，则执行下一步。以较大的数减去较小的数，然后用所得的差与较小的数比较，继续执行这个操作，直到所得的减数和差相等。第一步中约掉的若干个2与第二步中等数的乘积就是最大公约数。最小公倍数可以通过两个数的乘积除以最大公约数得到。

方法三：穷举法。该方法的步骤是，从1到较小的数逐个去除，找到两个数都能整除的最大的数，即为最大公约数。最小公倍数可以通过两个数的乘积除以最大公约数得到。

下面是几种方法的Python代码示例：

# 辗转相除法
a = int(input("请输入第一个数字："))
b = int(input("请输入第二个数字："))
m = a
n = b

while b != 0:
    temp = a % b
    a = b
    b = temp

max_common_divisor = a
min_common_multiple = m * n // a

print("最大公约数是：%d，最小公倍数是：%d" % (max_common_divisor, min_common_multiple))

# 更相减损法
a = int(input("请输入第一个数字："))
b = int(input("请输入第二个数字："))
m = a
n = b

if a < b:
    a, b = b, a

divisors = []
num = 1

if a % 2 == 0 and b % 2 == 0:
    a, b = a // 2, b // 2
    num *= 2

r = a - b

while r not in divisors:
    divisors.append(r)
    a = max(b, r)
    b = min(b, r)
    r = a - b

max_common_divisor = num * r
min_common_multiple = (m * n) // (num * r)

print("最大公约数是：%d，最小公倍数是：%d" % (max_common_divisor, min_common_multiple))

# 穷举法
a = int(input("请输入第一个数字："))
b = int(input("请输入第二个数字："))
m = a
n = b

while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a

max_common_divisor = a
min_common_multiple = (m * n) // a

print("最大公约数是：%d，最小公倍数是：%d" % (max_common_divisor, min_common_multiple))

以上是三种常用的方法，你可以根据需要选择其中一种方法来求解最大公约数和最小公倍数。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [Python求最大公约数和最小公倍数](https://blog.csdn.net/qq_46857088/article/details/124002509)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *2* *3* [python求最大公约数和最小公倍数的方法](https://blog.csdn.net/qq_40161609/article/details/82469855)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]