C语言——求两个数的最大公约数和最小公倍数

C语言——求两个数的最大公约数和最小公倍数求两个数的最大公约数的常用方法:※“辗转相除法”,又名欧几里得算法。基本方法如下:设两数为a和b(a>b),用a除以b,得a÷b=q……r,若r=0,则最大公约数为b;若r≠0,则再用b÷r,得b÷r=q……r’,若r’=0,则最大公约数为r’,若r’≠0,则继续用r÷r’……直到能够整除为止,此时的除数即为最大公约数。例如:a=99,b=18。a÷b=99÷18…

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

求两个数的最大公约数的常用方法:

※“辗转相除法”,又名欧几里得算法。基本方法如下:

设两数为a和b(a>b),用a除以b,得a÷b=q……r,若r=0 ,则最大公约数为b;若r≠0 ,则再用b÷r,得b÷r=q……r’,若r’=0,则最大公约数为r’,若r’≠0,则继续用r÷r’……直到能够整除为止,此时的除数即为最大公约数。

例如:a=99,b=18。a÷b=99÷18=5……9不能整除,则继续b÷r=18÷9=2可以整除,则此时的除数9即为a和b两数的最大公约数。

①代码如下:

#include <stdio.h>
int main()
{
	int a = 0;
	int b = 0;
	int t = 0;
	scanf("%d%d", &a, &b);//99,18
	while (a%b != 0){
		t = a%b;
		a = b;
		b = t;
	}
	printf("最大公约数为:%d\n", b);
	return 0;
}

首先,从键盘键入两个数a和b的值,变量t来保存余数。用while循环来判断能否整除,根据“辗转相除法”,先用第一个数a÷b再将除数b赋给a,余数赋给b,循环往复,直到能整除时结束循环,此时的除数b即为最大公约数。

(特别说明:若a<b,例如a=18,b=99。t=a%b=18;a=99;b=t=18。我们发现通过一次循环交换了a、b的值,这时就能满足a>b的条件了,在继续根据辗转相除的方法即可得到最大公约数。)

※拓展:求两个数的最小公倍数

关于最小公倍数与最大公约数,有这样的定理:最小公倍数×最大公约数=两数的乘积。

即:最小公倍数=两数的乘积÷最大公约数

②代码如下:

#include <stdio.h>
int main()
{
	int a = 0;
	int b = 0;
	int t = 0;
	scanf("%d%d", &a, &b);//18 99
	int m = a;
	int n = b;
	while (a%b != 0){
		t = a%b;//余数 9
		a = b;//18
		b = t;//9
	}
	printf("最大公约数为:%d\n", b);//9
	printf("最小公倍数为:%d\n",m*n/b);
	return 0;
}

首先,从键盘键入两个数a和b的值,变量t来保存余数。再设两个变量m、n来保存a、b的原值。

先根据辗转相除法求出最大公约数b’(过程同①),再由最小公倍数=两数的乘积÷最大公约数=m×n÷b’求得最小公倍数。


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

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

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

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

(0)


相关推荐

  • 职称计算机考试选什么模块,职称计算机考试如何选择模块?

    职称计算机考试选什么模块,职称计算机考试如何选择模块?原标题:职称计算机考试如何选择模块?众所周知,自从2013年开始,已有所增加,模块数理由原来的22个模块增加到26个考试科目。所以,考生可根据自身基础、平时接触多的或兴趣选择报考科目,按规定参加职称计算机考试的人员必须通过规定的模块数量,因各地区政策不同考生具体可登陆当地人事咨询网次查看,为了让考生更好选择职称计算机考试模块。职称计算机考试中心为考生提供如下参考:一、选择模块的原则:首先,根据考生…

  • 什么是旁路由 用旁路由有什么好处 旁路由怎么设置

    什么是旁路由 用旁路由有什么好处 旁路由怎么设置什么是旁路由用旁路由有什么好处旁路由怎么设置时间:2019-11-2315:48:52/来源:你好多多DIY/作者:多多2019年11月23日更新(初次发布于2019年5月13日)用旁路由和接二级路由的区别和好处:(PS:很多人吐槽旁路由这个词语非官方术语,甚至争的脸红耳赤,其实我们根本不需要太在意这个,对于普通用户来说,我们只要知道这个东西是什么,怎么用就行,比如电脑,也可以叫微机、计算机、甚至PC,何必那么纠结呢)区别:二级路由跟主路由的设备不在同一个网段;与主路由兼容性较差

  • eclipse自动补全设置_eclipse补全设置

    eclipse自动补全设置_eclipse补全设置Eclipse版本问题描述自动补全显示顺序不尽人意,如下:输入equals使用自动补全后,显然并不是我们希望使用的方法。解决方法1进入Windows选项卡下的Perferences,搜索ContentAssist,找到Java选项卡下的ContentAssist,选择Advanced选项卡。将其中内容配置为(即,将上下两部分的JavaProposals(Task-Focused)取消勾选,将JavaProposals勾选);之后就可以开心的使用自动补全啦!解决方法2这是

    2022年10月15日
  • 几种常见的ICMP报文类型

    几种常见的ICMP报文类型通过将一些常见的ICMP报文类型整理给大家,希望在需要的时候能帮助到大家。

  • 什么是pkl文件_桌面显示不出来怎么办是什么问题

    什么是pkl文件_桌面显示不出来怎么办是什么问题对于.pkl文件,我是在接触SMPL模型的时候用到的。SMPL的开源项目包里,有model文件夹,打开有两个.pkl文件。然后,找到了一个说的相对比较详细的网址https://jingyan.baidu.com/article/59a015e36ef251f794886598.html一、个人理解python中有一种存储方式,可以存储为.pkl文件。 该存储方式,可以将python项目过程中用到的一些暂时变量、或者需要提取、暂存的字符串、列表、字典等数据保存起来。 保存方式就是保存到创建的.p

  • 迅雷磁力bt链接下载器_种子搜索

    迅雷磁力bt链接下载器_种子搜索种子文件目录:C:\Users\jifeng\AppData\Local\Temp\magnetex

发表回复

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

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