要求两个数的最小公倍数（Least Common Multiple, LCM），可以先利用辗转相除法求出它们的最大公约数（Greatest Common Divisor, GCD），再根据最大公约数与最小公倍数的关系来计算最小公倍数。

原理

两个整数 a 和 b 的最小公倍数和最大公约数存在以下关系：

代码实现

下面是使用 C++ 实现利用辗转相除法求最小公倍数的代码，包含递归和迭代两种求最大公约数的方法：

#include <iostream>
#include <cmath>

// 递归实现辗转相除法求最大公约数
int gcdRecursive(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcdRecursive(b, a % b);
}

// 迭代实现辗转相除法求最大公约数
int gcdIterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 利用最大公约数求最小公倍数
int lcm(int a, int b) {
    int gcd = gcdIterative(a, b);
    return std::abs(a * b) / gcd;
}

int main() {
    int num1 = 12;
    int num2 = 18;

    // 使用递归方法求最大公约数
    int gcdRec = gcdRecursive(num1, num2);
    std::cout << "递归方法求得的最大公约数: " << gcdRec << std::endl;

    // 使用迭代方法求最大公约数
    int gcdIter = gcdIterative(num1, num2);
    std::cout << "迭代方法求得的最大公约数: " << gcdIter << std::endl;

    // 求最小公倍数
    int resultLcm = lcm(num1, num2);
    std::cout << "最小公倍数: " << resultLcm << std::endl;

    return 0;
}    

代码解释

1. gcdRecursive 函数：

   • 这是一个递归函数，用于求两个数的最大公约数。
   • 若 b 为 0，返回 a。
   • 否则，递归调用自身，传入 b 和 a % b 继续计算。

2. gcdIterative 函数：

   • 该函数使用迭代方式求最大公约数。
   • 利用 while 循环，不断更新 a 和 b 的值，直到 b 为 0。
   • 最终返回 a。

3. lcm 函数：

   • 先调用 gcdIterative 函数求出 a 和 b 的最大公约数。
   • 再根据公式 计算最小公倍数并返回。

4. main 函数：

   • 定义两个整数 num1 和 num2。
   • 分别使用递归和迭代方法求最大公约数并输出结果。
   • 调用 lcm 函数求最小公倍数并输出结果。

复杂度分析

辗转相除法，也被称作欧几里得算法，是一种用于计算两个整数的最大公约数（GCD）的经典算法。其核心思想是：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。接下来，我将详细介绍这个算法的原理、C++ 实现以及复杂度分析。

原理

设两个整数为 a 和 b（a >= b），它们的最大公约数记为 gcd(a, b)。根据辗转相除法，有如下关系：

• gcd(a, b) = gcd(b, a % b)
• 当 b 为 0 时，gcd(a, 0) = a

C++ 实现

下面是使用递归和迭代两种方式实现辗转相除法的 C++ 代码：

#include <iostream>

// 递归实现
int gcdRecursive(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcdRecursive(b, a % b);
}

// 迭代实现
int gcdIterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int num1 = 48;
    int num2 = 18;

    // 使用递归方法计算最大公约数
    int resultRecursive = gcdRecursive(num1, num2);
    std::cout << "递归方法计算的最大公约数: " << resultRecursive << std::endl;

    // 使用迭代方法计算最大公约数
    int resultIterative = gcdIterative(num1, num2);
    std::cout << "迭代方法计算的最大公约数: " << resultIterative << std::endl;

    return 0;
}

代码解释

1. 递归实现：

   • 函数 gcdRecursive 接收两个整数 a 和 b 作为参数。
   • 若 b 为 0，函数返回 a。
   • 否则，函数递归调用自身，参数变为 b 和 a % b。

2. 迭代实现：

   • 函数 gcdIterative 运用 while 循环来实现辗转相除法。
   • 在循环里，不断更新 a 和 b 的值，直到 b 为 0。
   • 最终返回 a。

3. 主函数：

   • 定义两个整数 num1 和 num2。
   • 分别调用递归和迭代函数来计算最大公约数，并输出结果。

复杂度分析

• 时间复杂度：辗转相除法的时间复杂度是 $O(log(min(a, b)))$，这意味着随着输入数值的增大，算法的执行时间增长较为缓慢。
• 空间复杂度：递归实现的空间复杂度为 $O(log(min(a, b)))$，这是由于递归调用会占用栈空间；迭代实现的空间复杂度为 $O(1)$，仅使用了常数级的额外空间。

通过上述教程，你可以掌握辗转相除法的原理和 C++ 实现，并且能够根据需求选择递归或迭代的方式来计算两个整数的最大公约数。