c语言怎么求最大公约数和最小公倍数
【c语言怎么求最大公约数和最小公倍数】在C语言中，求两个数的最大公约数（GCD）和最小公倍数（LCM）是常见的算法问题。这两个数在数学计算、编程优化以及实际应用中都具有重要意义。下面将总结如何通过C语言实现这两个功能，并以表格形式展示结果。
一、最大公约数（GCD）
最大公约数是指两个或多个整数共有约数中最大的一个。在C语言中，可以通过辗转相除法（也称为欧几里得算法）来求解最大公约数。
算法思路：
1. 输入两个正整数a和b。
2. 如果b为0，则a就是最大公约数。
3. 否则，用a除以b得到余数r，然后将a设为b，b设为r，重复步骤2。
示例代码：
```c
include
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
```
二、最小公倍数（LCM）
最小公倍数是指能被两个或多个整数整除的最小正整数。求最小公倍数可以通过以下公式：
$$
\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}
$$
因此，只要先求出最大公约数，就可以轻松计算出最小公倍数。
示例代码：
```c
include
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
int lcm(int a, int b) {
return (a b) / gcd(a, b);
}
```
三、运行结果对比表
| 输入数值 | 最大公约数（GCD） | 最小公倍数（LCM） |
| 12, 18 | 6 | 36 |
| 24, 36 | 12 | 72 |
| 7, 13 | 1 | 91 |
| 15, 25 | 5 | 75 |
| 9, 3 | 3 | 9 |
四、总结
在C语言中，求最大公约数和最小公倍数是基础但重要的算法练习。通过使用辗转相除法可以高效地找到最大公约数，而最小公倍数则可以通过最大公约数推导得出。掌握这些方法不仅有助于提升编程能力，也能加深对数学概念的理解。