1.最大公约数GCD
整数a和b的最大公约数记为gcd(a,b)。在编程中有以下的写法：
1）经典的欧几里得算法，用辗转相除法求最大公约数，模板如下：
//递归写法一：int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}//递归写法二：int gcd(int a, int b){if (a % b == 0) return b;else return gcd(b, a % b);}2)非递归写法：
int gcd(int a, int b){int temp = b;while (a % b){//辗转相除temp = a % b;a = b;b = temp;}return temp;}3)直接用C++内置函数求GCD
std::__gcd(a,b);2.最小公倍数LCM
最小公倍数=两数乘积/最大公约数
int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}int lcm(int a, int b){return a / gcd(a, b) * b;}上面是求两个数的最大公约数、最小公倍数，那么，两个以上的数字要求他们之间的最大公约数和最小公倍数要怎么实现呢？
3.求解多个数的最大公约数
1）暴力法
#include <iostream>using namespace std;int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}int main(){int a[8] = { 10,15,100,20,30,70,40,25 }; //最大公约数：5int L = sizeof(a) / sizeof(int); //L为元素个数int m = a[0];//初始化最大公约数：a[0]for (int i = 1; i < L; i++)//从a[1]开始{m = gcd(m, a[i]);}cout << m << endl;//输出最大公约数：5return 0;}让我们来分析一下 ，上面的写法虽然说很直观，但是在函数的实现过程中会不断调用内部有多次循环的gcd算法，在计算大数是比较复杂，推荐下面的优化算法：
以下的算法主要是采用两两求最大公约数的策略。首先初始化结果为数组第一个元素的值，然后依次用当前结果与下一个元素求最大公约数，直至最后一个元素。这种方法可以有效减少每步的计算量，特别是在数据规模较大时表现更为明显。
2）欧几里得算法的扩展
#include <iostream>using namespace std;// 求两个整数的最大公约数int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b);}// 求多个整数的最大公约数int gcd_multiple(int a[], int L) { int result = a[0]; // 初始化为第一个元素的值 for (int i = 1; i < L; i++) { result = gcd(result, a[i]); // 依次求当前结果和下一个元素的最大公约数 if (result == 1) { // 如果已经是1，可以提前结束计算，因为1是所有数的公约数 return 1; } } return result;}int main() { int a[8] = {10, 15, 100, 20, 30, 70, 40, 25}; // 给定数组 int L = sizeof(a) / sizeof(int); // 数组长度 int m = gcd_multiple(a, L); // 调用函数求多个数的最大公约数 cout << "最大公约数：" << m << endl; return 0;} 这是我们还可以继续优化，使用 std::sort 函数对数组 a 进行排序。排序后，数组的元素按照从小到大的顺序排列。在排序后的数组中，从最小的数开始逐个计算与当前结果的最大公约数。这样可以确保每一步的计算都使用较小的数，减少每步的计算量和次数。
3）使用std::sort函数进行优化
#include <iostream>#include <algorithm> // 包含 sort 函数using namespace std;// 求两个整数的最大公约数int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b);}// 求多个整数的最大公约数int gcd_multiple(int a[], int L) { sort(a, a + L); // 对数组 a 进行排序 int result = a[0]; // 初始化为最小值 for (int i = 1; i < L; i++) { result = gcd(result, a[i]); // 依次求当前结果和下一个元素的最大公约数 if (result == 1) { // 如果已经是1，可以提前结束计算，因为1是所有数的公约数 return 1; } } return result;}int main() { int a[8] = {10, 15, 100, 20, 30, 70, 40, 25}; // 给定数组 int L = sizeof(a) / sizeof(int); // 数组长度 int m = gcd_multiple(a, L); // 调用函数求多个数的最大公约数 cout << "最大公约数：" << m << endl; return 0;}4.求解多个数的最小公倍数
思路：先求出前两个数的最小公倍数(a)，再用这个最小公倍数(a)与下一个数求出它们的最小公倍数(b)，不断循环直到计算完所有数。
#include <iostream> #include <vector> #include <algorithm> // 为了使用std::gcd using namespace std;// 辅助函数：计算两个数的最大公约数（GCD） // 这里使用C++17的std::gcd，如果编译器不支持，可以自定义实现 int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}// 求解多个数的最小公倍数（LCM） int lcmOfNumbers(const vector<int>& nums) {int lcm = 1; // 初始化LCM为1 for (int num : nums) {// 对于每一个数，更新LCM为当前LCM与该数的LCM lcm = (lcm * num) / gcd(lcm, num);}return lcm;}int main() {// 测试数据 vector<int> numbers = { 2, 3, 5, 7 };// 调用函数求解最小公倍数 int lcm = lcmOfNumbers(numbers);// 输出结果 cout << "多个数的最小公倍数为: " << lcm << endl;return 0;}