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)


相关推荐

  • js——promise用法

    js——promise用法.1.promise基本用法<script>constpromise=newPromise((resolve,reject)=>{console.log(1);resolve(5);console.log(2)}).then(val=>{console.log(val);});pro

  • 小米bl未解锁变砖了如何刷机_如何正确刷机

    小米bl未解锁变砖了如何刷机_如何正确刷机1.一部可以解锁bl的手机选择一部合适可以解锁的手机,以小米为例(我有的),小米需要绑定账号在新手机15天。去小米官方申请(https://www.miui.com/unlock/index.html),登陆账号,下载解锁工具,在工具里面登录小米账号,数据线连接进入bl模式的手机.(解锁会清空手机数据).解锁后手机仍保修登录小米账号,下载解锁工具2.选择合适的twrp下载twrp后,电脑使用…

  • win10 loadrunner11_windows10重装系统步骤

    win10 loadrunner11_windows10重装系统步骤一.初识LoadRunner( 点击链接跳转到LoadRunner的安装步骤)1.简介:(1)从LoadRunner英语字面上进行理解就是负载跑步者,为什么这么说呢?对于从事IT软件行业的工作者如开发人员和测试人员来说一定不会感到陌生就是在承受负载的条件下运行软件或者网页的业务。从另一…

    2022年10月14日
  • 面试了一个5年的Java,问什么都说不会…!

    面试了一个5年的Java,问什么都说不会…!最近看了很多简历,很多候选人年限不小,但是做的都是一些非常传统的项目,想着也不能通过简历就直接否定一个人,何况现在大环境越来越难,大家找工作也不容易,…

  • JDBC_5 DBUtils[通俗易懂]

    JDBC_5 DBUtils[通俗易懂]DBUtilscommons-dbutils是Apache组织提供的一个开源JDBC工具类库,封装了针对于数据库的增删改查操作APIQueryRunnerResulSetHandlerDbutils插入举例Connection conn = null; try { QueryRunner runner = new QueryRunner(); conn = JBBCUtils.getConnections3();

  • 《Python 快速入门》C站最全Python标准库总结

    《Python 快速入门》C站最全Python标准库总结❤粉丝福利:免费下载海量【PPT模板、简历模板、学习资料】

发表回复

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

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