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

【C语言】求最小公倍数和最大公约数(辗转相除法)用到的名词:最小公倍数,最大公约数,辗转相除法一、名词解释:1).最小公倍数:最小公倍数(LeastCommonMultiple,LCM),如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数,对于两个整数来说,指该两数共有倍数中最小的一个。计算最小公倍数时,通常会借助最大公约数来辅助计算。 最小公倍数=两数的乘积/最大公约(因)数,解题时要避免和最大公约(因)…

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

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

一、名词解释:

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.手机用户(贴图):

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

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.效果图:

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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/145322.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号