怎么求最大公约数和最小公倍数

求最大公约数和最小公倍数的方法有很多种，下面是两种常用的方法：

1. 辗转相除法

辗转相除法又称欧几里得算法，其基本思想是用大数除以小数，然后用余数代替原来的大数，一直重复这个步骤，直到余数为零为止，此时小数就是最大公约数。

最小公倍数可以根据最大公约数求出，即两个数的积除以它们的最大公约数。

以下是辗转相除法的示例代码：

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)

2. 穷举法

穷举法的基本思想是从两个数中较小的一个开始，逐步减小，直到找到两个数都能整除的最大数为止，此即为最大公约数。最小公倍数可以根据最大公约数求出，即两个数的积除以它们的最大公约数。

以下是穷举法的示例代码：

def gcd(a, b):
    if a > b:
        smaller = b
    else:
        smaller = a
    for i in range(1, smaller+1):
        if((a % i == 0) and (b % i == 0)):
            gcd = i
    return gcd

def lcm(a, b):
    return a * b // gcd(a, b)

以上两种方法都可以求出最大公约数和最小公倍数，但辗转相除法更加高效，因此常用于实际应用中。