【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)


相关推荐

  • windows10 系统设置一键备份

    windows10 系统设置一键备份1、打开pe下优启通桌面的EIX系统安装;2、分区备份—–C盘——-新建映像文件3、选择保存路径,非C盘,重命名;4、一键备份5、确认;

  • pycharm创建mysql数据库_自学语言的步骤

    pycharm创建mysql数据库_自学语言的步骤Python连接mysql并进行一些基本操作之前有讲过Python如何连接Oracle,在这一期。在连接mysql数据库时,原理相同,这里我们先说明理论部分,再给出一个具体实例。Python操作MySQL数据库需要下载PyMySQL.PyMySQL是一个Python编写的MySQL驱动程序。安装代码:pipinstallPyMySQL在Python中建立连接,先导入包:导入代码为:importpymysql#创建连接:连接代码:通过工具类调用connect()方法。注意:(必

  • debugview使用方法_debugger怎么用

    debugview使用方法_debugger怎么用1、什么是DebugView?DebugView是一个系统调试信息输出的捕获工具。2、DebugView它能干吗?可以捕获程序中由TRACE()和OutputDebugString()输出的信息。说的具体一点,在程序中使用如下函数:1)、OutputDebugString 或者在MFC中使用TRACE2)、内核模式中使用Out_Deb

    2022年10月28日
  • Pytest(16)随机执行测试用例pytest-random-order「建议收藏」

    Pytest(16)随机执行测试用例pytest-random-order「建议收藏」前言通常我们认为每个测试用例都是相互独立的,因此需要保证测试结果不依赖于测试顺序,以不同的顺序运行测试用例,可以得到相同的结果。pytest默认运行用例的顺序是按模块和用例命名的ASCII编码

  • Visifire组件应用

    Visifire组件应用本文转载自:http://www.cnblogs.com/forgetu/archive/2010/06/07/Visifire-AxisLabels.html这篇中简单介绍一下Axis(坐标轴)的主要的几个属性的设置。Visifire废话少说,主要的几个属性及属性的设置和意思请看下面的示例代码和注释:viewsource…

  • 如何统计项目代码(比如微信小程序等等)

    如何统计项目代码(比如微信小程序等等)

发表回复

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

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