当前位置：首页 > article >正文

c++最大公约数和最小公倍数的深入剖析

article 2024/12/27 18:24:51

一、概念基础

二、常见算法及深度解析

1. 辗转相除法（欧几里得算法）

2. 更相减损术

3. 结合辗转相除法和更相减损术（优化算法）

三、应用场景全面举例

1. 化简分数

2. 判断互质关系

一、什么是最小公倍数

二、求最小公倍数的常见算法思路（基于 C++）

（一）暴力枚举法

（二）利用最大公约数（GCD）来求

三、多变量求最小公倍数

四、最小公倍数在实际编程中的应用场景

（一）任务调度问题

（二）分数运算中的通分

五、性能优化与注意事项

（一）溢出问题

（二）算法效率优化

一、利用最大公约数（GCD）求最小公倍数

二、质因数分解法

三、使用 C++ 标准库中的 lcm 函数（C++17 及以上版本支持）

利用最大公约数（GCD）求最小公倍数

1. 理论基础

2. 求最大公约数的欧几里得算法（辗转相除法）实现细节

3. 利用求出的最大公约数计算最小公倍数

质因数分解法

1. 原理深入剖析

2. C++ 代码详细实现与步骤解释

使用 C++ 标准库中的 lcm 函数（C++17 及以上版本支持）

1. 函数介绍与使用示例

2. 适用场景与优势

一、概念基础

最大公约数（Greatest Common Divisor，GCD）作为数论中的一个关键概念，在多个整数之间发挥着重要作用。从数学定义来讲，对于给定的两个或多个整数，其最大公约数就是能够同时整除这些整数的最大正整数。

例如，考虑整数 12 和 18：

12 的所有约数（即能够整除 12 的正整数）包括 1、2、3、4、6、12。
18 的所有约数有 1、2、3、6、9、18。
通过对比它们的约数集合，可以清晰地发现共有的约数为 1、2、3、6，其中数值最大的 6 就是 12 和 18 的最大公约数。

在更广泛的数学和编程应用场景中，最大公约数有着诸多用途。比如在分数运算里化简分数时，必须依靠最大公约数将分子分母化为最简形式，以保证运算结果的准确性和规范性；在判断两个数是否互质（即它们的最大公约数为 1）方面也起着决定性作用，而互质这一特性在密码学、数论算法等诸多领域都有着关键应用，像一些加密算法在生成密钥等操作时会要求所选的数是互质的，这就需要通过计算最大公约数来进行验证。

二、常见算法及深度解析

1. 辗转相除法（欧几里得算法）

算法原理：
辗转相除法基于一个重要的定理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。具体操作过程是，用较大的整数除以较小的整数，得到一个商和余数，然后将除数作为新的被除数，余数作为新的除数，不断重复这个除法过程，直到余数为 0 时，此时的除数就是原来两个数的最大公约数。

以计算 252 和 105 的最大公约数为例来详细说明这个过程：

首先，252 ÷ 105 = 2……42，这里 2 是商，42 是余数。
接着，把 105 作为被除数，42 作为除数，即 105 ÷ 42 = 2……21。
再把 42 作为被除数，21 作为除数，42 ÷ 21 = 2……0，此时余数为 0，所以 21 就是 252 和 105 的最大公约数。
代码实现细节及分析：
以下是使用 C++ 实现辗转相除法求最大公约数的函数代码：

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while (b!= 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

在这段代码中：

函数gcd接受两个整数参数a和b，代表要求最大公约数的两个数。
通过while循环来不断执行辗转相除的操作，只要余数b不为 0，就持续更新a和b的值。具体来说，先将当前的b值保存到临时变量temp中，然后让b等于a除以b的余数（b = a % b），再把temp（也就是原来的b）赋值给a，实现了被除数和除数的更新，这个过程模拟了辗转相除的数学步骤。
当b最终变为 0 时，循环结束，此时的a就是最初输入的两个数的最大公约数，函数返回该值。
算法复杂度分析：
辗转相除法在时间复杂度方面有着良好的性能表现。在最坏的情况下，例如求两个连续的斐波那契数（如F(n)和F(n - 1)，F(n)表示第n个斐波那契数）的最大公约数时，其时间复杂度接近O(log n)，这里的n是指两个输入数中较大的那个数。在平均情况下，它的运算效率也比较高，这使得它在实际的编程应用中被广泛采用，尤其是处理较大规模整数求最大公约数的场景时，能够快速得出结果，减少计算时间和资源消耗。

2. 更相减损术

算法原理：
更相减损术是我国古代数学中的杰出算法成果，其核心思想是：以较大的数减去较小的数，然后用所得的差与较小的数再次比较大小，并继续以大数减小数的操作，如此反复进行，直到所得的减数和差相等为止，这个相等的值就是原来两个数的最大公约数。

例如，计算 98 和 63 的最大公约数：

首先，98 - 63 = 35。
接着，63 - 35 = 28。
然后，35 - 28 = 7。
再接着，28 - 7 = 21。
继续，21 - 7 = 14。
最后，14 - 7 = 7，此时减数和差相等，所以 7 就是 98 和 63 的最大公约数。
代码实现细节及分析：
以下是用 C++ 实现更相减损术求最大公约数的代码示例：

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while (a!= b) {
        if (a > b) {
            a -= b;
        } else {
            b -= a;
        }
    }
    return a;
}

在这段代码里：

函数gcd同样接收两个整数a和b作为输入参数。
通过while循环来持续执行相减操作，只要a和b不相等，就判断它们的大小关系。如果a大于b，就用a减去b，更新a的值；反之，如果b大于a，就用b减去a，更新b的值。这样不断循环，直到a和b相等，此时的a（也就是相等后的这个值）就是最大公约数，最后函数返回该值。
算法复杂度分析：
更相减损术的时间复杂度在最坏情况下相对较高，可能达到O(max(a, b))，这里a和b是输入的两个数。也就是说，在某些极端情况下，比如两个数相差非常大且需要多次相减操作时，计算次数会随着输入数的大小而增加较多。不过，在一些数据分布相对均匀的实际场景中，其实际运算次数可能并不会特别多，但总体来讲，相较于辗转相除法，在多数常规应用场景下，它的效率会稍低一些，不过由于其蕴含的独特数学思想以及在一些特定领域的应用价值，依然值得深入了解。

3. 结合辗转相除法和更相减损术（优化算法）

算法原理：
这种优化算法巧妙地结合了前两者的优势。首先，利用更相减损术对于偶数的处理优势，当两个数a和b均为偶数时，先将它们都除以 2，同时记录下除掉的 2 的个数（可以通过一个变量，每次除以 2 时就让其自乘 2 来实现对 2 的幂次方的记录），然后对得到的新的a和b（此时至少有一个是奇数）使用辗转相除法来求最大公约数，最后将通过辗转相除法得到的最大公约数乘上之前除掉的 2 的个数对应的 2 的幂次方，这样得到的结果就是原来a和b的最大公约数。

例如，对于 48 和 36 这两个数：

第一步，发现它们都是偶数，48÷2 = 24，36÷2 = 18，同时记录因子 2（假设用变量factor表示，初始值为 1，此时factor = 2）。
接着，24 和 18 还是偶数，继续操作，24÷2 = 12，18÷2 = 9，factor更新为factor *= 2，即factor = 4。
此时，12 和 9 中只有 12 是偶数，不符合均为偶数的条件了，对 12 和 9 使用辗转相除法：12÷9 = 1……3，9÷3 = 3……0，得到最大公约数为 3。
最后，将这个 3 乘以之前记录的factor（值为 4），得到 12，这就是 48 和 36 的最大公约数。
代码实现细节及分析：
以下是结合辗转相除法和更相减损术求最大公约数的 C++ 代码示例：

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    int factor = 1;
    while (a % 2 == 0 && b % 2 == 0) {
        a /= 2;
        b /= 2;
        factor *= 2;
    }
    while (b!= 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a * factor;
}

在代码中：

首先定义了变量factor并初始化为 1，用于记录除掉的 2 的幂次方。
通过第一个while循环来处理a和b均为偶数的情况，只要a和b都能被 2 整除，就分别除以 2，并让factor乘以 2 来更新其值，这样不断提取公因子 2，直到a和b至少有一个不再是偶数。
接着，使用第二个while循环执行辗转相除法，其原理和前面单独介绍辗转相除法时的代码逻辑一致，通过不断更新a和b的值，直到b为 0，此时得到的a是经过前面处理后的a和b的最大公约数。
最后，将这个通过辗转相除法得到的最大公约数a乘以factor，得到的就是最初输入的a和b的最大公约数，函数返回该最终结果。
算法复杂度分析：
这种优化算法由于先通过快速处理偶数情况，有效地减少了后续辗转相除法的运算规模，整体的时间复杂度依然接近O(log n)，这里的n同样是指输入的两个数中较大的那个数。不过在处理一些较大且含有较多 2 因子的数时，相比单纯的辗转相除法，它能够通过提前去除大量的 2 因子，从而减少辗转相除的迭代次数，运算速度会更快一些，在对效率要求较高的一些大规模数据处理或者数论相关复杂应用场景中，有着较好的优势。

三、应用场景全面举例

1. 化简分数

在数学的分数运算中，化简分数是一个常见操作。例如，对于分数12/18，要将其化为最简分数形式，就需要求出分子 12 和分母 18 的最大公约数。通过前面介绍的求最大公约数的算法（比如使用辗转相除法，求得 12 和 18 的最大公约数为 6），然后将分子分母同时除以这个最大公约数，即12÷6 = 2，18÷6 = 3，得到最简分数2/3。

在 C++ 编程中，如果要实现一个分数类，在类的构造函数或者专门的化简方法中，就可以调用求最大公约数的函数来完成分数的化简操作。以下是一个简单的分数类示例代码，其中包含了利用最大公约数化简分数的功能：

#include <iostream>
using namespace std;

class Fraction {
private:
    int numerator;  // 分子
    int denominator;  // 分母
public:
    Fraction(int num, int den) : numerator(num), denominator(den) {
        simplify();
    }
    void simplify() {
        int gcd_value = gcd(numerator, denominator);
        numerator /= gcd_value;
        denominator /= gcd_value;
    }
    void display() {
        cout << numerator << "/" << denominator << endl;
    }
    int gcd(int a, int b) {
        while (b!= 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
};

int main() {
    Fraction fraction(12, 18);
    fraction.display();
    return 0;
}

在这个代码中：

Fraction类表示分数，有numerator（分子）和denominator（分母）两个私有成员变量。
构造函数接受分子和分母作为参数，并在初始化对象时调用simplify方法来化简分数。
simplify方法通过调用类内部定义的gcd函数（实现了辗转相除法求最大公约数）求出分子分母的最大公约数，然后将分子分母分别除以这个最大公约数来完成化简。
display方法用于输出化简后的分数形式。

2. 判断互质关系

判断两个数是否互质在很多领域都有着重要应用，特别是在数论和密码学相关算法中。如果两个数的最大公约数为 1，那么就称这两个数是互质的。

例如，在密码学的一些加密算法中，比如 RSA 算法（一种非对称加密算法），在生成公钥和私钥的过程中，需要选择两个互质的大素数作为参数的一部分。通过编写 C++ 程序调用求最大公约数的函数来判断给定的两个数是否互质，进而决定是否符合算法要求进行下一步的密钥生成等操作。以下是一个简单的判断互质关系的 C++ 代码示例：

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while (b!= 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

bool areCoprime(int a, int b) {
    return gcd(a, b) == 1;
}

int main() {
    int num1 = 13, num2 = 17;
    if (areCoprime(num1, num2)) {
        cout << num1 << " 和 " << num2 << " 是互质的" << endl;
    } else {
        cout << num1 << " 和 " << num2 << " 不是互质的" << endl;
    }
    return 0;
}

在这段代码中：

首先定义了gcd函数用于求两个数的最大公约数（采用辗转相除法实现）。
然后定义了areCoprime函数，它通过调用gcd函数获取两个数的最大公约数，并判断这个最大公约数是否等于 1，如果等于 1 就返回true，表示这两个数是互质的；否则返回false。
在main函数中，给定两个数（这里是 13 和 17），调用areCoprime函数来判断它们是否互质，并根据返回结果输出相应的提示信息。

总之，在 C++ 编程领域，深入理解最大公约数的概念、熟练掌握不同的求最大公约数算法及其复杂度特点、清晰知晓其丰富的应用场景，对于解决众多涉及数论基础以及具有相关逻辑要求的编程问题都有着不可或缺的重要意义，无论是在数学计算相关的程序开发，还是在诸如密码学等专业领域的算法实现中，都能发挥关键作用。

一、什么是最小公倍数

在数学领域，特别是整数范畴内，最小公倍数有着明确且重要的定义。对于给定的两个或多个整数，最小公倍数是指能够被这些整数同时整除的最小的正整数。

例如，考虑整数 3 和 4，能被 3 整除的数有 3、6、9、12、15 等等，能被 4 整除的数有 4、8、12、16 等等。可以发现 12 是第一个既能被 3 整除又能被 4 整除的最小正整数，所以 3 和 4 的最小公倍数就是 12。

再比如三个整数 2、3 和 4，能同时被这三个数整除的正整数序列中，最小的那个数是 12，也就是它们的最小公倍数。

从集合的角度来看，如果把能被一个整数整除的所有正整数看作一个集合，那么最小公倍数就是这些集合的交集里最小的那个正整数元素。

二、求最小公倍数的常见算法思路（基于 C++）

（一）暴力枚举法

这种方法的思路非常直观，它基于最小公倍数的定义直接去寻找满足条件的数值。

具体步骤如下：

首先确定两个整数 a 和 b，找出它们当中较大的那个数，记为 max_num，一般可以通过 max(a, b) 函数（C++ 标准库 <algorithm> 中提供的函数，用于比较两个值并返回较大值）来获取。
接着从 max_num 开始，进入一个无限循环（while (true)），在每次循环中进行判断：
- 检查当前的 max_num 是否能同时被 a 和 b 整除，也就是判断 max_num % a == 0 并且 max_num % b == 0 是否同时成立。这里的 % 是 C++ 中的取余运算符，如果取余结果为 0，则说明能整除。
- 若上述条件满足，意味着找到了最小公倍数，此时就可以使用 return max_num; 返回这个值，结束函数的执行。
- 若条件不满足，就将 max_num 的值增加 1（max_num++），然后继续下一轮循环，继续去检查新的 max_num 值是否满足条件。

以下是对应的 C++ 代码示例：

#include <iostream>
#include <algorithm>
using namespace std;

int lcm_brute_force(int a, int b) {
    int max_num = max(a, b);
    while (true) {
        if (max_num % a == 0 && max_num % b == 0) {
            return max_num;
        }
        max_num++;
    }
}

不过，这种方法存在明显的缺点，当 a 和 b 的数值较大时，可能需要执行非常多次的循环才能找到最小公倍数，导致程序运行效率低下，消耗较多的计算时间和资源。

（二）利用最大公约数（GCD）来求

这是一种基于数学原理的高效求最小公倍数的方法，它利用了两个整数的最小公倍数与最大公约数之间的内在关系。

数学原理是：对于两个整数 a 和 b，它们的最小公倍数 LCM(a, b) 等于它们的乘积除以它们的最大公约数，即 LCM(a, b) = a * b / GCD(a, b)。

所以，要通过这种方法求最小公倍数，首先需要求出两个数的最大公约数，常用的方法是欧几里得算法（辗转相除法），其原理和步骤如下：

假设有两个整数 a 和 b（不妨设 a >= b），进入一个循环，循环条件是 b!= 0。
在循环体中，先把当前的 b 值保存到一个临时变量 temp 中（int temp = b;），这是因为后面会改变 b 的值，需要临时保存一下当前 b 的状态。
然后将 b 的值更新为 a % b，这里的 % 是取余运算，也就是用 a 除以 b 的余数来更新 b 的值，这一步实现了辗转相除的核心操作，不断缩小两个数的规模。
接着把之前保存的 temp（也就是原来的 b 值）赋值给 a（a = temp;），完成一次辗转相除的迭代。
当 b 的值变为 0 时，循环结束，此时的 a 值就是原来 a 和 b 的最大公约数。

对应的 C++ 代码实现如下：

int gcd(int a, int b) {
    while (b!= 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

在求出最大公约数后，就可以利用上述的数学关系来计算最小公倍数了，代码如下：

int lcm_gcd(int a, int b) {
    return a * b / gcd(a, b);
}

这种方法相比暴力枚举法效率更高，它巧妙地借助了最大公约数这个中间结果，避免了大量不必要的循环试探，尤其是在处理较大数值时，优势更为明显。

三、多变量求最小公倍数

当需要求多个整数（比如 a、b、c……）的最小公倍数时，可以采用逐步求解的策略。

具体做法如下：

先取数组（假设用数组 arr 存放这些整数，n 表示数组元素个数）中的第一个元素 arr[0] 作为初始的最小公倍数结果值（int result = arr[0];）。
然后从数组的第二个元素开始（索引为 1，通过 for (int i = 1; i < n; i++) 循环），依次将当前的最小公倍数结果值 result 和数组中的下一个元素 arr[i] 利用前面提到的基于最大公约数求最小公倍数的方法（lcm_gcd 函数）来计算新的最小公倍数，并更新 result 的值（result = lcm_gcd(result, arr[i]);）。
如此循环下去，直到遍历完数组中的所有元素，此时的 result 值就是这多个整数的最小公倍数。

以下是对应的 C++ 代码示例：

int multi_lcm(int arr[], int n) {
    int result = arr[0];
    for (int i = 1; i < n; i++) {
        result = lcm_gcd(result, arr[i]);
    }
    return result;
}

四、最小公倍数在实际编程中的应用场景

（一）任务调度问题

在很多操作系统或者软件系统中，存在着多个周期性任务需要执行。例如，在一个服务器程序里，可能有一个数据备份任务每隔 6 小时需要执行一次，还有一个日志清理任务每隔 8 小时需要执行一次。

为了合理安排这些任务，使得系统资源能高效利用并且不会出现任务冲突等问题，就需要找到一个合适的时间间隔，在这个时间间隔后，所有的任务都能同时再次启动执行。这个时间间隔就是这些任务周期的最小公倍数，在上述例子中，6 和 8 的最小公倍数是 24，也就意味着每隔 24 小时，数据备份任务和日志清理任务会同时再次执行，这样可以方便地对这些任务进行统一的调度管理，提高系统整体的稳定性和效率。

（二）分数运算中的通分

在编写程序处理分数的加减法、比较大小等运算时，往往需要先对分数进行通分操作。通分就是要把参与运算的各个分数化为分母相同的分数，而这个相同的分母通常就是原来各个分数分母的最小公倍数。

例如，要计算 1/3 + 1/4，首先需要找到 3 和 4 的最小公倍数 12，然后将 1/3 化为 4/12，1/4 化为 3/12，这样就可以进行同分母分数的加法运算，得到 7/12。在实现分数运算相关的程序功能时，准确高效地计算最小公倍数就成为了关键的环节，关乎整个分数运算的正确性和程序的可靠性。

五、性能优化与注意事项

（一）溢出问题

在利用 a * b / GCD(a, b) 这个公式计算最小公倍数时，很容易出现整数溢出的情况。因为如果 a 和 b 的数值比较大，它们的乘积 a * b 可能会超出整数类型所能表示的范围。比如在 C++ 中，int 类型通常有一定的取值范围（一般是 -2147483648 到 2147483647），当 a 和 b 相乘的结果超过这个范围时，就会发生溢出错误，导致计算结果不正确。
为了解决这个问题，可以采取多种措施。一种是使用更大的数据类型，比如 long long 类型，它能表示的数值范围更大，在一定程度上可以避免因乘积过大而溢出的情况。例如：

long long lcm_gcd_long(long long a, long long b) {
    return a * b / gcd(a, b);
}

另一种方式是对计算逻辑进行调整，例如，如果 a 和 b 都是偶数，可以先将它们都除以 2，然后再计算最小公倍数，最后乘以 2 的相应幂次（取决于总共除掉了几个 2）。或者先进行除法运算（如果能保证 a 和 b 能整除 GCD(a, b) 的话）再进行乘法运算，这样也能在一定程度上降低溢出的风险，不过这种方法需要对数据的性质有更细致的判断和处理。

（二）算法效率优化

虽然利用最大公约数求最小公倍数的方法相对暴力枚举法已经高效很多，但在一些对性能要求极高的场景下，还可以进一步探索优化的空间。比如，可以研究一些基于更先进数论原理的算法，像扩展欧几里得算法的一些拓展应用等，不过这些往往需要更深入的数学知识储备，并且要根据具体的应用场景去权衡优化所带来的性能提升和实现这些复杂算法所增加的代码复杂度之间的关系。
另外，在多变量求最小公倍数的逐步求解过程中，可以考虑对数据进行预处理，比如先对数组中的整数进行排序，从较小的数开始逐步计算，有时候可能会减少一些不必要的计算量，提高整体的运算速度，但这也需要通过实际的测试和具体情况来判断是否真的能带来显著的性能提升。

总之，在 C++ 中深入理解和掌握最小公倍数的计算方法及应用场景，对于解决众多涉及整数关系、周期性任务安排以及数学运算相关的编程问题有着至关重要的意义。同时，要充分考虑到可能出现的溢出等问题，并根据实际需求对算法进行合理的优化，以确保程序的正确性、高效性以及可靠性。

除了暴力枚举法，以下是一些其他求最小公倍数的常见方法（基于 C++ 实现）：

一、利用最大公约数（GCD）求最小公倍数

原理：
根据数学原理，对于两个整数 a 和 b，它们的最小公倍数 LCM(a, b) 等于它们的乘积除以它们的最大公约数，即 LCM(a, b) = a * b / GCD(a, b)。所以只要能求出两个数的最大公约数，就能方便地算出最小公倍数。
求最大公约数的欧几里得算法（辗转相除法）示例代码及步骤：

int gcd(int a, int b) {
    while (b!= 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

步骤如下：

设有两个整数 a 和 b（不妨设 a >= b），进入循环，循环条件是 b!= 0。
在循环体中，先将当前 b 值暂存到 temp 变量中（int temp = b;）。
接着把 b 更新为 a % b（b = a % b;），实现辗转相除，不断缩小两数规模。
再把暂存的 temp（原来的 b 值）赋值给 a（a = temp;），完成一次迭代。
当 b 值变为 0 时，循环结束，此时 a 就是 a 和 b 的最大公约数。

利用求出的最大公约数计算最小公倍数的代码示例：

int lcm_gcd(int a, int b) {
    return a * b / gcd(a, b);
}

这种方法相对高效，避免了暴力枚举中大量的循环试探，在处理较大数值时优势明显。

二、质因数分解法

原理：
先分别对两个数进行质因数分解，找出它们所有的质因数以及每个质因数的最高次幂。然后将所有质因数按照其最高次幂相乘，所得的结果就是这两个数的最小公倍数。
例如，求 12 和 18 的最小公倍数：

对 12 进行质因数分解可得： $12=2^{2}\times3 ^{1}$ 。

对 18 进行质因数分解可得： $18=2^{1}\times3 ^{1}$ 。

综合来看，质因数 2 的最高次幂是 2，质因数 3 的最高次幂是 2，所以最小公倍数为 $2^{2}\times 3^{2}=36$

C++ 代码示例及步骤：

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// 辅助函数，判断一个数是否为质数
bool isPrime(int num) {
    if (num < 2) return false;
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) return false;
    }
    return true;
}

// 对一个数进行质因数分解，返回质因数及其次数的映射（用pair表示）
vector<pair<int, int>> primeFactorization(int num) {
    vector<pair<int, int>> factors;
    int n = num;
    for (int i = 2; i <= num; i++) {
        if (isPrime(i) && num % i == 0) {
            int count = 0;
            while (num % i == 0) {
                num /= i;
                count++;
            }
            factors.push_back(make_pair(i, count));
        }
    }
    return factors;
}

// 求两个数的最小公倍数（基于质因数分解）
int lcm_primeFactorization(int a, int b) {
    vector<pair<int, int>> factors_a = primeFactorization(a);
    vector<pair<int, int>> factors_b = primeFactorization(b);

    int lcm = 1;
    int i = 0, j = 0;
    while (i < factors_a.size() || j < factors_b.size()) {
        int factor;
        int power_a = (i < factors_a.size())? factors_a[i].second : 0;
        int power_b = (j < factors_b.size())? factors_b[j].second : 0;

        if (i < factors_a.size() && j < factors_b.size() && factors_a[i].first == factors_b[j].first) {
            factor = factors_a[i].first;
            lcm *= pow(factor, max(power_a, power_b));
            i++;
            j++;
        } else if (i < factors_a.size() && (j >= factors_b.size() || factors_a[i].first < factors_b[j].first)) {
            factor = factors_a[i].first;
            lcm *= pow(factor, power_a);
            i++;
        } else {
            factor = factors_b[j].first;
            lcm *= pow(factor, power_b);
            j++;
        }
    }
    return lcm;
}

步骤如下：

首先编写辅助函数，如 isPrime 函数用于判断一个数是否为质数，方便后续找出质因数。
接着 primeFactorization 函数对给定的数进行质因数分解，通过循环从最小质数 2 开始，不断判断能否整除给定数，若能整除则记录该质因数以及其出现的次数，直到给定数被分解完。
在 lcm_primeFactorization 函数中，先分别对两个数 a 和 b 进行质因数分解得到相应的质因数及其次数的向量表示。
然后通过循环比较两个数的质因数情况，取每个质因数的最高次幂，累乘到 lcm 变量中，最终得到最小公倍数。

这种方法在理解数的因数结构方面比较直观，但代码实现相对复杂一些，涉及较多的循环和判断逻辑。

三、使用 C++ 标准库中的 `lcm` 函数（C++17 及以上版本支持）

在 C++17 及之后的版本中，标准库 <numeric> 里新增了 std::lcm 函数，可以直接用来求两个整数（或更多整数，支持可变参数形式）的最小公倍数，使用起来非常方便。示例代码如下：

#include <iostream>
#include <numeric>
using namespace std;

int main() {
    int a = 12, b = 18;
    int result = std::lcm(a, b);
    cout << "The least common multiple of " << a << " and " << b << " is: " << result << endl;
    return 0;
}

使用该函数时，只需传入相应的整数参数即可快速得到最小公倍数，不过要注意编译器需支持 C++17 及以上标准，否则无法使用这个函数。

这些方法各有优劣，可以根据具体的编程场景、对效率和代码复杂度的要求等因素来选择合适的求最小公倍数的方式。

以下是对除暴力枚举法之外的求最小公倍数的几种方法更为详细的介绍：

利用最大公约数（GCD）求最小公倍数

1. 理论基础

在数论中，两个整数 a 和 b 的最小公倍数与最大公约数存在着紧密的数学关系，即 LCM(a, b) = a * b / GCD(a, b)。这个关系可以通过以下方式来理解：

设 a 和 b 的质因数分解分别为：
a = p1^e1 * p2^e2 *... * pn^en（其中 p1, p2,..., pn 是质数，e1, e2,..., en 是对应的指数）
b = p1^f1 * p2^f2 *... * pn^fn

那么它们的最大公约数 GCD(a, b) 就是 p1^min(e1,f1) * p2^min(e2,f2) *... * pn^min(en,fn)，而最小公倍数 LCM(a, b) 是 p1^max(e1,f1) * p2^max(e2,f2) *... * pn^max(en,fn)。

由于 a * b = (p1^e1 * p2^e2 *... * pn^en) * (p1^f1 * p2^f2 *... * pn^fn) = p1^(e1 + f1) * p2^(e2 + f2) *... * pn^(en + fn)，同时根据指数运算中 max(ei, fi) + min(ei, fi) = ei + fi 的性质，就可以推导出 LCM(a, b) = a * b / GCD(a, b) 这一公式。

2. 求最大公约数的欧几里得算法（辗转相除法）实现细节

以下是用 C++ 实现的欧几里得算法（辗转相除法）求最大公约数的代码：

int gcd(int a, int b) {
    while (b!= 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

具体的执行过程和每一步的解释如下：

初始化：
给定两个整数 a 和 b（假设 a >= b），进入循环，循环条件是 b 不为 0，因为当 b 变为 0 时，此时的 a 值就是最大公约数。
循环迭代：
在每次循环中：
- 首先，使用一个临时变量 temp 来保存当前 b 的值（int temp = b;）。这一步很关键，因为接下来要改变 b 的值，而后续还需要用到原来 b 的值来更新 a 。
- 然后，通过取余运算 a % b 来更新 b 的值（b = a % b;）。例如，若 a = 24，b = 18，第一次迭代时 a % b 即 24 % 18 = 6，此时 b 的值就变为 6。这个操作实际上是在不断缩小两个数的规模，利用了辗转相除的原理，将较大数除以较小数取余数，用余数替换原来较小的数，反复进行这个过程。
- 最后，把之前保存的 temp（也就是原来的 b 值）赋值给 a（a = temp;）。继续上面的例子，a 的值就从 24 变为 18。这样就完成了一次辗转相除的迭代过程。
结束条件与结果返回：
循环会一直执行，直到 b 的值变为 0。此时的 a 值就是最初输入的 a 和 b 两个数的最大公约数。例如，对于 a = 18，b = 6，经过一次迭代后 b 变为 0，此时 a 的值 6 就是 18 和 6 的最大公约数。

3. 利用求出的最大公约数计算最小公倍数

在求出最大公约数后，利用 LCM(a, b) = a * b / GCD(a, b) 这个公式来计算最小公倍数就很简单了，代码如下：

int lcm_gcd(int a, int b) {
    return a * b / gcd(a, b);
}

例如，若 a = 12，b = 18，首先通过 gcd 函数求出它们的最大公约数为 6，然后根据公式计算 12 * 18 / 6 = 36，即 12 和 18 的最小公倍数是 36。

这种方法相对暴力枚举法效率更高，尤其是在处理较大数值时，因为它避免了大量无意义的逐个数值试探，而是通过巧妙地先求出最大公约数这个关键中间量来快速得到最小公倍数。

质因数分解法

1. 原理深入剖析

质因数分解法的核心思路是基于整数的质因数分解特性来求最小公倍数。每个整数都可以唯一地分解成一系列质数的乘积，形式为 n = p1^e1 * p2^e2 *... * pk^ek，其中 p1, p2,..., pk 是不同的质数，e1, e2,..., ek 是它们对应的指数。

对于要求最小公倍数的两个整数 a 和 b，分别进行质因数分解后，为了得到能同时被 a 和 b 整除的最小正整数（即最小公倍数），需要取每个质因数在 a 和 b 分解式中出现的最高次幂，然后将这些质因数按照其最高次幂相乘，所得结果就是最小公倍数。

例如，求 24 和 36 的最小公倍数：

对 24 进行质因数分解：
24 = 2^3 * 3^1（因为 24 = 2 * 2 * 2 * 3，即 2 出现了 3 次，3 出现了 1 次）。
对 36 进行质因数分解：
36 = 2^2 * 3^2（36 = 2 * 2 * 3 * 3，2 出现 2 次，3 出现 2 次）。

对比它们的质因数分解式，质因数 2 在 24 中的最高次幂是 3，在 36 中的最高次幂是 2，所以取 3；质因数 3 在 24 中的最高次幂是 1，在 36 中的最高次幂是 2，所以取 2。

那么最小公倍数就是 2^3 * 3^2 = 72，这样就能保证得到的数既能被 24 整除又能被 36 整除，且是满足此条件的最小正整数。

2. C++ 代码详细实现与步骤解释

以下是用 C++ 实现质因数分解法求最小公倍数的完整代码及各部分的详细解释：

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// 辅助函数，判断一个数是否为质数
bool isPrime(int num) {
    if (num < 2) return false;
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) return false;
    }
    return true;
}

// 对一个数进行质因数分解，返回质因数及其次数的映射（用pair表示）
vector<pair<int, int>> primeFactorization(int num) {
    vector<pair<int, int>> factors;
    int n = num;
    for (int i = 2; i <= num; i++) {
        if (isPrime(i) && num % i == 0) {
            int count = 0;
            while (num % i == 0) {
                num /= i;
                count++;
            }
            factors.push_back(make_pair(i, count));
        }
    }
    return factors;
}

// 求两个数的最小公倍数（基于质因数分解）
int lcm_primeFactorization(int a, int b) {
    vector<pair<int, int>> factors_a = primeFactorization(a);
    vector<pair<int, int>> factors_b = primeFactorization(b);

    int lcm = 1;
    int i = 0, j = 0;
    while (i < factors_a.size() || j < factors_b.size()) {
        int factor;
        int power_a = (i < factors_a.size())? factors_a[i].second : 0;
        int power_b = (j < factors_b.size())? factors_b[j].second : 0;

        if (i < factors_a.size() && j < factors_b.size() && factors_a[i].first == factors_b[j].first) {
            factor = factors_a[i].first;
            lcm *= pow(factor, max(power_a, power_b));
            i++;
            j++;
        } else if (i < factors_a.size() && (j >= factors_b.size() || factors_a[i].first < factors_b[j].first)) {
            factor = factors_a[i].first;
            lcm *= pow(factor, power_a);
            i++;
        } else {
            factor = factors_b[j].first;
            lcm *= pow(factor, power_b);
            j++;
        }
    }
    return lcm;
}

各函数功能及执行步骤解释如下：

isPrime 函数：
这是一个辅助函数，用于判断一个数是否为质数。其原理是，对于一个大于等于 2 的整数 num，从 2 开始到该数的平方根（通过 sqrt(num) 获取）依次检查能否整除 num，如果能被其中某个数整除，那就不是质数，返回 false；如果遍历完这个范围都不能整除，说明是质数，返回 true。例如，判断 7 是否为质数，从 2 到 sqrt(7)（约 2.6）的整数只有 2，7 不能被 2 整除，所以 7 是质数，函数返回 true。
primeFactorization 函数：
这个函数的功能是对给定的整数 num 进行质因数分解，并以 vector<pair<int, int>> 的形式返回结果，其中每个 pair 的第一个元素是质因数，第二个元素是该质因数在分解中的次数。
具体执行步骤如下：
- 首先初始化一个空的向量 factors 用于存储质因数及其次数，将传入的 num 赋值给 n（int n = num;），方便后续操作过程中对原 num 值的修改。
- 然后从最小的质数 2 开始（for (int i = 2; i <= num; i++)），在循环中，先通过 isPrime 函数判断当前的 i 是否为质数，并且检查 num 是否能被 i 整除（if (isPrime(i) && num % i == 0)），如果满足这两个条件，说明找到了一个质因数 i。
- 接着进入一个内层循环（while (num % i == 0)），在这个循环里，每次将 num 除以 i，并记录次数（count++），直到 num 不能再被 i 整除为止。例如，对 24 进行分解，当 i = 2 时，内层循环会执行 3 次，因为 24 可以连续被 2 整除 3 次，此时 count 的值变为 3，然后将 pair(2, 3) 加入到 factors 向量中，表示找到了质因数 2，其出现次数为 3。
- 当外层循环遍历完从 2 到 num 的所有数后，factors 向量就完整地记录了 num 的质因数分解情况，最后将其返回。
lcm_primeFactorization 函数：
此函数用于根据两个数的质因数分解结果求出它们的最小公倍数。
执行步骤如下：
- 首先分别调用 primeFactorization 函数对输入的两个数 a 和 b 进行质因数分解，得到对应的质因数及其次数的向量表示 factors_a 和 factors_b。
- 初始化最小公倍数 lcm 为 1（int lcm = 1;），并设置两个索引变量 i 和 j 分别用于遍历 factors_a 和 factors_b 向量，初始值都为 0。
- 进入一个 while 循环（while (i < factors_a.size() || j < factors_b.size())），这个循环的目的是比较两个数的质因数分解情况，取每个质因数的最高次幂来计算最小公倍数，循环条件表示只要还有未处理完的质因数就继续循环。
- 在循环体中，首先获取当前比较位置的质因数在 a 和 b 中的次数（如果索引未超出对应向量范围），分别存放在 power_a 和 power_b 变量中（int power_a = (i < factors_a.size())? factors_a[i].second : 0; 等语句）。
- 接着通过条件判断来处理不同情况：
  - 如果当前位置 i 和 j 对应的质因数相同（if (i < factors_a.size() && j < factors_b.size() && factors_a[i].first == factors_b[j].first)），那么取这个质因数，并将其按照最高次幂累乘到 lcm 中（lcm *= pow(factor, max(power_a, power_b));），然后同时将 i 和 j 索引后移一位。
  - 如果 i 对应的质因数还未处理完且满足特定条件（else if (i < factors_a.size() && (j >= factors_b.size() || factors_a[i].first < factors_b[j].first))），说明当前 a 中的质因数在 b 中不存在或者还未出现，那就将这个质因数按照其在 a 中的次数累乘到 lcm 中，并将 i 索引后移一位。
  - 否则（即 j 对应的质因数情况符合上述未处理完的条件），将 b 中的质因数按照其在 b 中的次数累乘到 lcm 中，并将 j 索引后移一位。
- 当循环结束后，lcm 的值就是 a 和 b 的最小公倍数，最后将其返回。

这种质因数分解法在理解整数的因数结构以及数与数之间的整除关系方面比较直观，但代码实现相对复杂，涉及较多的循环嵌套、条件判断以及向量操作等逻辑，不过在一些特定的数学分析场景或者对原理理解要求较高的应用中很有帮助。

使用 C++ 标准库中的 `lcm` 函数（C++17 及以上版本支持）

1. 函数介绍与使用示例

在 C++17 及之后的版本中，标准库 <numeric> 里新增了 std::lcm 函数，它提供了一种非常便捷的求最小公倍数的方式，可以直接用来求两个整数（或更多整数，支持可变参数形式）的最小公倍数。

以下是一个简单的使用示例代码：

#include <iostream>
#include <numeric>
using namespace std;

int main() {
    int a = 12, b = 18;
    int result = std::lcm(a, b);
    cout << "The least common multiple of " << a << " and " << b << " is: " << result << endl;
    return 0;
}

在上述代码中，首先包含了 <numeric> 头文件，这个头文件中定义了 std::lcm 函数。然后定义了两个整数 a 和 b，通过调用 std::lcm(a, b) 函数就可以直接获取它们的最小公倍数，并将结果存储在 result 变量中，最后输出显示。