考研真题C语言

【2015年山西大学考研真题】输入两个正整数m和n，求最大公约数和最小公倍数。

对于两个正整数?m?和?n，求最大公约数（GCD）和最小公倍数（LCM）的算法如下：

1.?首先用辗转相除法求最大公约数：
???-?如果?n?等于?0，则?GCD(m,?n)?=?m；
???-?否则，GCD(m,?n)?=?GCD(n,?m?%?n)。

2.?求最小公倍数：
???-?首先计算两个数的乘积?m?*?n；
???-?然后，最小公倍数?LCM(m,?n)?=?m?*?n?/?GCD(m,?n)。

下面是使用?C?语言描述这个算法的代码：

```c
#include?<stdio.h>

//?求最大公约数
int?gcd(int?m,?int?n)?{
????if?(n?==?0)?{
????????return?m;
????}

????return?gcd(n,?m?%?n);
}

//?求最小公倍数
int?lcm(int?m,?int?n)?{
????return?m?*?n?/?gcd(m,?n);
}

int?main()?{
????int?m,?n;

????printf("请输入两个正整数：");
????scanf("%d?%d",?&m,?&n);

????int?gcdResult?=?gcd(m,?n);
????int?lcmResult?=?lcm(m,?n);

????printf("最大公约数：%d\n",?gcdResult);
????printf("最小公倍数：%d\n",?lcmResult);

????return?0;
}
```

在上述代码中，我们定义了两个函数?`gcd`?和?`lcm`?来求最大公约数和最小公倍数。在?`main`?函数中，我们读取输入的两个正整数，然后调用这两个函数来进行计算并输出结果。

算法的时间复杂度依赖于辗转相除法的递归次数，它是?O(log(min(m,?n)))。算法的空间复杂度为?O(1)。

?