最大公约数与最小公倍数c++

### 计算最大公约数和最小公倍数 #### 最大公约数 通过欧几里得算法可以高效地计算两个整数的最大公约数。该方法基于这样一个事实：如果 \( R = A \mod B \)，则 \( g \) 是 \( A \) 和 \( B \) 的最大公约数当且仅当它也是 \( B \) 和 \( R \) 的最大公约数[^5]。 下面是使用 C++ 编写的欧几里得算法来求解两个整数的最大公约数： ```cpp #include <iostream> using namespace std; // 使用欧几里得算法求最大公约数 int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } int main() { int num1 = 48, num2 = 18; cout << "The GCD of " << num1 << " and " << num2 << " is: " << gcd(num1, num2) << endl; return 0; } ``` 上述代码实现了 `gcd` 函数，用于返回两数的最大公约数[^1]。 --- #### 最小公倍数 最小公倍数可以通过以下关系式计算得出： \[ \text{LCM}(a, b) = \frac{|a \times b|}{\text{GCD}(a, b)} \] 这意味着一旦我们得到了两个数的最大公约数，就可以轻松得到它们的最小公倍数。下面是一个完整的程序示例，展示如何同时计算最大公约数和最小公倍数： ```cpp #include <iostream> using namespace std; // 求最大公约数函数 int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } // 求最小公倍数函数 long long lcm(int a, int b) { return static_cast<long long>(a) * b / gcd(a, b); } int main() { int num1 = 12, num2 = 18; cout << "The GCD of " << num1 << " and " << num2 << " is: " << gcd(num1, num2) << endl; cout << "The LCM of " << num1 << " and " << num2 << " is: " << lcm(num1, num2) << endl; return 0; } ``` 在这个例子中，`lcm` 函数利用了之前定义好的 `gcd` 函数来完成最小公倍数的计算[^3]。 --- #### 多个数的情况 对于多个数的最大公约数或最小公倍数，我们可以依次应用二元运算的结果到整个数组上。例如，在处理一组数时，可以从第一个数开始逐步与其他数进行最大公约数或最小公倍数的操作。 以下是针对多个数的最大公约数的一个简单实现： ```cpp #include <iostream> using namespace std; // 求最大公约数函数 int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } int main() { int nums[] = {10, 15, 100, 20, 30, 70, 40, 25}; int length = sizeof(nums) / sizeof(nums[0]); int result = nums[0]; for (int i = 1; i < length; ++i) { result = gcd(result, nums[i]); } cout << "The GCD of the array is: " << result << endl; return 0; } ``` 此代码片段展示了如何遍历一个数组并逐次调用 `gcd` 来找到这些数的整体最大公约数。 --- #### 总结 以上提供了几种不同的方式来使用 C++ 实现最大公约数和最小公倍数的计算。无论是简单的双数值情况还是更复杂的多数值场景，都可以借助于基本的欧几里得算法及其扩展形式得以解决。