【C语言】求最小公倍数和最大公约数(辗转相除法)

全栈程序员-站长 • 2022年5月17日下午5:40 • 未分类 • 阅读 30

大家好，又见面了，我是你们的朋友全栈君。

用到的名词:最小公倍数，最大公约数，辗转相除法

一、名词解释:

1).最小公倍数:

最小公倍数（Least Common Multiple，LCM），如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数，对于两个整数来说，指该两数共有倍数中最小的一个。计算最小公倍数时，通常会借助最大公约数来辅助计算。

最小公倍数=两数的乘积/最大公约（因）数，解题时要避免和最大公约（因）数问题混淆。

对于最小公倍数的求解，除了利用最大公约数外，还可根据定义进行算法设计。要求任意两个正整数的最小公倍数即，求出一个最小的能同时被两整数整除的自然数。

2).最大公约数

如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。

根据约数的定义可知，某个数的所有约数必不大于这个数本身，几个自然数的最大公约数必不大于其中任何一个数。要求任意两个正整数的最大公约数即求出一个不大于其中两者中的任何一个，但又能同时整除两个整数的最大自然数。

3).辗转相除法

辗转相除法，又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

二、算法思想

利用格式输入语句将输入的两个数分别赋给 a 和 b，然后判断 a 和 b 的关系，如果 a 小于 b，则利用中间变量 t 将其互换。再利用辗转相除法求出最大公约数，进而求出最小公倍数。最后用格式输出语句将其输出。

三、代码实现:

1.手机用户(贴图):

2.代码:

#include <stdio.h>
  2 int main()
  3 {
  4     int a,b,c,m,t;
  5     printf("请输入两个数:\n");
  6     scanf("%d%d",&a,&b);
  7     if(a<b)
  8     {
  9         t=a;
 10         a=b;
 11         b=t;
 12     }
 13     m=a*b;
 14     c=a%b;
 15     while(c!=0)
 16     {
 17         a=b;
 18         b=c;
 19         c=a%b;
 20     }
 21     printf("最大公约数是:\n%d\n",b);
 22     printf("最小公倍数是:\n%d\n",m/b);
 23 }

3.效果图: