c语言用辗转相除法求最大公约数和最小公倍数
时间: 2023-11-08 18:56:46 浏览: 122
辗转相除法,求最大公约数和最小公倍数
5星 · 资源好评率100%
好的,我知道你要问关于C语言用辗转相除法求最大公约数和最小公倍数的问题。辗转相除法,也称欧几里得算法,是求解两个整数的最大公约数的常用方法之一。其基本想法是用较小数除较大数,再用出现的余数去除除数,直到余数为零为止。而最小公倍数则可以通过先求最大公约数,然后通过两数之积除以最大公约数得到。以下是C语言代码实现:
```c
#include <stdio.h>
int main()
{
int a, b, x, y, t, gcd, lcm;
printf("Enter two integers:\n");
scanf("%d %d", &x, &y);
a = x;
b = y;
// 求最大公约数
while (b != 0)
{
t = b;
b = a % b;
a = t;
}
gcd = a;
// 求最小公倍数
lcm = x * y / gcd;
printf("Greatest common divisor of %d and %d is %d\n", x, y, gcd);
printf("Least common multiple of %d and %d is %d\n", x, y, lcm);
return 0;
}
```
其中,a和b是两个需要求最大公约数的整数,x和y是输入的两个整数,t用于交换变量的值,gcd和lcm分别存放最大公约数和最小公倍数的结果。
阅读全文