c++用辗转相除法求最大公约数和最小公倍数
时间: 2024-09-22 19:06:18 浏览: 43
在 C++ 中,可以使用欧几里得算法(也称为辗转相除法或更相减损术)来求两个整数的最大公约数(Greatest Common Divisor, GCD)。这个算法基于这样一个原理:两个整数的最大公约数等于其中较小的那个数和两数余数的最大公约数。
以下是简单的 C++ 代码示例:
```cpp
#include <iostream>
int gcd(int a, int b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}
// 使用上面的gcd函数计算最小公倍数(LCM)
int lcm(int a, int b) {
int temp = gcd(a, b);
return (a * b) / temp;
}
int main() {
int num1, num2;
std::cout << "请输入两个整数:";
std::cin >> num1 >> num2;
std::cout << "最大公约数(GCD)为:" << gcd(num1, num2) << "\n";
std::cout << "最小公倍数(LCM)为:" << lcm(num1, num2) << "\n";
return 0;
}
```
在这个例子中,`gcd` 函数递归地应用辗转相除法则,直到找到 `b` 等于 0 的情况。然后,`lcm` 函数利用 `gcd` 计算结果和原始两个数乘积除以 `gcd` 的值,即得到最小公倍数。
阅读全文