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

最小公倍数和最大公约数可以用辗转相乘法求解。首先，求出两个数的最大公约数，然后用两个数的乘积除以最大公约数就可以得到最小公倍数。具体步骤如下：

1. 将两个数中较大的数除以较小的数，得到商和余数。
2. 如果余数为0，则较小的数就是最大公约数。
3. 如果余数不为0，则用较小的数除以余数，得到商和新的余数。
4. 重复步骤3，直到余数为0为止，此时较小的数就是最大公约数。
5. 最小公倍数等于两个数的乘积除以最大公约数。

例如，求36和48的最大公约数和最小公倍数：

36 ÷ 48 = 0 余36
48 ÷ 36 = 1 余12
36 ÷ 12 = 3 余0
因此，36和48的最大公约数是12，最小公倍数是144。

相关问题

2、输入两个正整数 m和n，求出它们的最大公约数和最小公倍数。 算法描述： （1）用辗转相除法求最大公约数+ m对n求余为a，若a不等于0，则 m-n，，n=a，继续求余，否则 n 为最大公约数， （2） 最小公倍数=两个数的积/最大公约数 c程序

为了计算两个正整数 `m` 和 `n` 的最大公约数（GCD，Greatest Common Divisor）和最小公倍数（LCM，Least Common Multiple），你可以使用以下步骤：

1. **辗转相除法求最大公约数**（欧几里得算法）：
- 初始化 a 为 n，b 为 m（因为我们要找的是 b 和 a 的 GCD，所以先用较大的作为 a）
- 当 b 不等于 0 时，将 a 赋值给 b，同时将 b 被 a 除后的余数赋值给 a
- 继续这个过程，直到 b 变为 0。此时，a 就是最大公约数。

int gcd(int m, int n) {
    if (n == 0)
        return m;
    else
        return gcd(n, m % n);
}

2. **计算最小公倍数**：
- 使用公式 LCM(a, b) = |a * b| / GCD(a, b)，其中 "|" 表示取绝对值。如果 m 和 n 都是非负数，那么可以直接用乘法计算，然后除以最大公约数；如果是负数，需要先取绝对值再计算。

int lcm(int m, int n) {
    int abs_m = m > 0 ? m : -m;
    int abs_n = n > 0 ? n : -n;
    return (abs_m * abs_n) / gcd(abs_m, abs_n);
}

用函数嵌套的方法求两个数的最大公约数及最小公倍数

可以使用辗转相除法和最大公约数与最小公倍数的关系，将求最大公约数和最小公倍数的过程封装成两个函数。

代码如下：

def gcd(a, b):
    """
    求两个数的最大公约数
    """
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(a, b):
    """
    求两个数的最小公倍数
    """
    return a * b // gcd(a, b)

其中，`gcd`函数使用递归的方式实现辗转相除法，求出最大公约数；`lcm`函数则使用最大公约数与最小公倍数的关系，通过整除和乘法运算求出最小公倍数。