目录

• 1 题目
• 2 分析
• • 2.1 辗转相除法
  • 2.2 相减法
• 3 实现
• • 3.1 实现1（辗转相除法）
  • 3.2 实现2（相减法）

1 题目

输入两个正整数m和n，求其最大公约数和最小公倍数。

2 分析

求最大公约数和最小公倍数这里给出两种实现方法，实际上只用求最大公约数即可，因为在数学上最小公倍数有这样的关系，所求的两个数的积即为其最大公约数和最小公倍数的积，所以只求出其中一个，另一个便能直接计算出来。

注：这里只给出通俗的计算方法，并不给出严格数学证明过程。

2.1 辗转相除法

辗转相除法求两个数的最大公约数的步骤如下，假如两个数为 $a$ 和 $b$：

用大的数 $a$ 除以小的数 $b$，得第一个余数 $c$；

再用上一步计算中小的那个数除以上一步中的余数，即 $b$ 除以 $c$，得第二个余数 $d$；

重复上两步；

直到余数是0为止.那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）

程序见实现3.1

2.2 相减法

假如两个数为 $a$ 和 $b$：

若 $a>b$，则 $a=a-b$

若 $a<b$，则 $b=b-a$

若 $a=b$，则 $a$（或 $b$）即为两数的最大公约数

若 $a$ ≠ $b$，则再回去执行第一步

程序见实现3.2

3 实现

3.1 实现1（辗转相除法）

#include <stdio.h>int main() {int n, m;int temp;printf("请输入n和m，中间用空格分隔：");scanf("%d%d", &n, &m);// 将较大的那个数赋值给a，较小的那个数赋值给bif (m > n) {temp = m;m = n;n = temp;}int a = n;int b = m;// 利用辗转相除法计算最大公约数while (b != 0) {temp = a % b;a = b;b = temp;}printf("最大公约数是%d\n", a);printf("最小公倍数是%d\n", n * m / a);return 0; }

3.2 实现2（相减法）

#include <stdio.h>int main() {int a, b ;printf("请输入a和b，中间用空格分隔：");scanf ("%d%d", &a, &b);int m = a;int n = b; // 当a, b不相等，用大数减小数，直到相等为止while (a != b) {if (a > b) {a = a - b;} else {b = b - a;}}printf("最大公约数是%d\n", a);printf("最小公倍数是%d\n", m * n / a); }

总结

以上是生活随笔为你收集整理的C语言经典例16-最大公约数和最小公倍数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。