求两个数的最大公因数（GCD）和最小公倍数（LCM）是编程中的一个常见问题。以下是几种常见的算法及其对应的代码实现：
1. 辗转相除法（Euclidean Algorithm）
辗转相除法是求最大公因数的一种经典算法。其基本思想是：两个正整数a和b（a > b）的最大公因数等于a除以b的余数c和b之间的最大公因数。具体步骤如下：
1. 初始化一个循环，令较大数为a，较小数为b。
2. 在循环中，用较大数除以较小数，得到余数。
3. 将较大数更新为较小数，将余数更新为较大数。
4. 重复步骤2和3，直到较小数为0。
5. 最大公因数即为初始的较大数。
代码实现（C++）：
```cpp
include using namespace std； int gcd（int a, int b） { while （b != 0） { int temp = a % b； a = b； b = temp； } return a； } int main（） { int a, b； cout << "请输入两个整数：" << endl； cin >> a >> b； cout << "最大公因数是：" << gcd（a, b） << endl； return 0； } ``` 2. 更相损减法 更相损减法是另一种求最大公因数的方法，适用于任何需要求最大公约数的场合。其步骤如下： 1. 设两数为a, b，其中a做被除数，b做除数，c为余数。 2. 大数放a中，小数放b中。 3. 求a/b的余数。 4. 若c=0则b为最大公约数。 5. 如果c!=0则把b的值给a，c的值给b。 6. 返回第二步。 代码实现（C++）： ```cpp include using namespace std； int gcd（int a, int b） { while （a % b != 0） { int temp = a % b； a = b； b = temp； } return b； } int main（） { int a, b； cout << "请输入两个数：" << endl； cin >> a >> b； cout << "最大公约数为：" << gcd（a, b） << endl； return 0； } ``` 3. 暴力枚举法 暴力枚举法是一种简单直接的方法，从较大的那个数开始，从大到小枚举，找到一个共同的因数，然后退出循环。 代码实现（C++）： ```cpp include using namespace std； int gcd（int a, int b） { if （b == 0） return a； if （a % b == 0） return b； return gcd（b, a % b）； } int main（） { int a, b； cout << "请输入两个数：" << endl； cin >> a >> b； cout << "最大公因数是：" << gcd（a, b） << endl； return 0； } ``` 4. Stein算法 Stein算法是一种基于数论的高效算法，适用于大整数的最大公因数计算。其步骤如下： 1. 初始化a = b，b = a % b。 2. 如果b = 0，则a即为最大公因数。 3. 如果b != 0，则令a = b，b = a % b，重复步骤2。 代码实现（C++）： ```cpp include using namespace std； int gcd（int a, int b） { while （b != 0） { int temp = a % b； a = b； b = temp； } return a； } int main（） { int a, b； cout << "请输入两个数：" << endl； cin >> a >> b； cout << "最大公因数是：" << gcd（a, b） << endl； return 0； } ```