辗转相除法是一种非常有效的方法，用于计算两个整数的最大公约数（Greatest Common Divisor, GCD）和最小公倍数（Least Common Multiple, LCM）。这种方法基于一个简单的数学原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

让我们先来了解一下如何使用辗转相除法求解最大公约数。假设我们有两个整数a和b，且a > b，那么它们的最大公约数可以通过不断将较大的数替换为较小的数，较小的数替换为两数相除后的余数，直到余数为0为止。此时，最后的非零余数即为所求的最大公约数。

接下来，我们来看看如何利用最大公约数来计算最小公倍数。最小公倍数可以通过以下公式得到：LCM(a, b) = (a b) / GCD(a, b)。

下面是一个用C++实现辗转相除法的例子：

```cpp

include

using namespace std;

// 求最大公约数

int gcd(int a, int b) {

if (b == 0)

return a;

else

return gcd(b, a % b);

}

// 求最小公倍数

int lcm(int a, int b) {

return (a b) / gcd(a, b);

}

int main() {

int num1, num2;

cout << "请输入两个整数: ";

cin >> num1 >> num2;

cout << "最大公约数是: " << gcd(num1, num2) << endl;

cout << "最小公倍数是: " << lcm(num1, num2) << endl;

return 0;

}

```

通过这个程序，我们可以轻松地计算出任意两个整数的最大公约数和最小公倍数。希望这篇介绍能帮助大家更好地理解和应用辗转相除法！✨

标 签：