最大公约数和最小倍数 c语言
时间: 2024-10-14 18:01:06 浏览: 6
最大公约数(Greatest Common Divisor, GCD)是指两个或多个整数共有的最大的正因数。在C语言中,可以使用欧几里得算法(Euclidean Algorithm)来计算最大公约数。该算法的基本思想是利用辗转相除法,即较大的数除以较小的数,然后用余数替换原来较小的数,继续做同样的操作,直到余数为0,此时的除数就是两数的最大公约数。
至于最小公倍数(Least Common Multiple, LCM),它是两个或多个整数的公共倍数中最小的一个。计算最小公倍数通常与最大公约数有关,因为两数的乘积等于它们的最大公约数和最小公倍数的乘积(a * b = gcd(a, b) * lcm(a, b))。所以,在C语言中,一旦有了最大公约数,可以通过这个公式来得到最小公倍数。
下面是一个简单的示例代码片段:
```c
#include <stdio.h>
// 求最大公约数 (欧几里得算法)
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;
printf("请输入两个数字:");
scanf("%d %d", &num1, &num2);
// 输出最大公约数和最小公倍数
printf("最大公约数: %d\n", gcd(num1, num2));
printf("最小公倍数: %d\n", lcm(num1, num2));
return 0;
}
```
阅读全文