辗转相除法求最大公约数最小公倍数,c语言
时间: 2023-11-17 11:59:34 浏览: 51
辗转相除法是一种求解两个正整数最大公约数的算法,也可以用来求最小公倍数。在C语言中,可以使用while循环来实现辗转相除法。
以下是求解最大公约数和最小公倍数的C语言代码:
```c
#include <stdio.h>
int main()
{
int m, n, a, b, c, gcd, lcm;
printf("请输入两个正整数m和n:\n");
scanf("%d%d", &m, &n);
a = m;
b = n;
while (b != 0)
{
c = a % b;
a = b;
b = c;
}
gcd = a;
lcm = m * n / gcd;
printf("最大公约数为:%d\n", gcd);
printf("最小公倍数为:%d\n", lcm);
return 0;
}
```
解释一下代码:
首先,我们定义了四个变量m、n、gcd和lcm,其中m和n是输入的两个正整数,gcd和lcm是最大公约数和最小公倍数。
然后,我们使用scanf函数从用户输入中读取m和n的值。
接下来,我们使用while循环来实现辗转相除法。在循环中,我们使用变量a和b来保存m和n的值,使用变量c来保存余数。在每次循环中,我们将a赋值给b,将b赋值给c,然后计算a除以b的余数,将结果保存在c中。当b等于0时,循环结束,此时a的值就是m和n的最大公约数。
最后,我们使用公式lcm = m * n / gcd来计算最小公倍数,并输出最大公约数和最小公倍数的值。