【c语言怎么求最大公约数和最小公倍数】在C语言中，求两个数的最大公约数（GCD）和最小公倍数（LCM）是常见的算法问题。这两个数的计算方法虽然不同，但它们之间有密切的关系：最小公倍数 = 两数之积 ÷ 最大公约数。因此，在实际编程中，通常先求出最大公约数，再通过公式计算最小公倍数。
下面将从原理、代码实现和结果示例三个方面对这两个问题进行总结。
一、原理说明
1. 最大公约数（GCD）
最大公约数是指两个或多个整数共有约数中最大的一个。常用的方法有：
- 辗转相除法（欧几里得算法）：用较大的数除以较小的数，然后用余数代替较大的数，重复这个过程，直到余数为0，此时的除数即为最大公约数。
- 穷举法：从1到较小的数依次判断是否能同时整除两个数，找到最大的那个。
2. 最小公倍数（LCM）
最小公倍数是指能被两个或多个整数同时整除的最小正整数。可以通过以下公式计算：
$$
\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}
$$
二、C语言实现方式
下面是使用C语言实现求最大公约数和最小公倍数的代码示例：
```c
include
// 函数声明
int gcd(int a, int b);
int lcm(int a, int b);
int main() {
int num1, num2;
printf("请输入两个整数：");
scanf("%d %d", &num1, &num2);
printf("最大公约数是：%d\n", gcd(num1, num2));
printf("最小公倍数是：%d\n", lcm(num1, num2));
return 0;
}
// 辗转相除法求最大公约数
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// 利用GCD计算最小公倍数
int lcm(int a, int b) {
return (a b) / gcd(a, b);
}
```
三、运行结果示例
| 输入数值 | 最大公约数 | 最小公倍数 |
| 12, 18 | 6 | 36 |
| 24, 36 | 12 | 72 |
| 7, 13 | 1 | 91 |
| 5, 10 | 5 | 10 |
| 15, 20 | 5 | 60 |
四、总结
在C语言中，求最大公约数和最小公倍数的核心在于掌握辗转相除法的实现逻辑。通过该方法可以高效地求出GCD，再利用公式快速计算出LCM。这种算法不仅效率高，而且易于理解和实现，是解决此类问题的推荐方法。
对于初学者来说，建议多动手编写代码并测试不同的输入，以加深对算法的理解。
