C语言求两个数的最大公约数、最小公倍数(三种方法)

2024-04-30 10:18

本文主要是介绍C语言求两个数的最大公约数、最小公倍数(三种方法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

最大公约数:也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。(如果数a能被数b整除,a就叫做b的倍数,b就叫做a的约数)

最小公倍数:两个或多个整数公有的倍数叫做它们的公倍数,其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。

以两个整数为例,我们知道最小公倍数=两整数乘积 / 最大公约数。那么在求出最大公约数的基础下,利用该公式便可求出最小公倍数。

那么如何求两个数的最大公约数,最小公倍数呢?

法一:

我们通常是先比较两个数的大小,找到较小的一个。然后让这两个数都对 以较小数为首的递减序列(增量为-1) 求余,如果两个数同时都能被其整除,则找到最大公约数。

int main()
{int a = 17, b = 35;int n, i;//找a,b中较小的数if (a > b){n = b;}else{n = a;}for ( i = n; i > 0; i--){if (a%i == 0 && b%i == 0){printf("最大公约数为%d\n", i);printf("最小公倍数为%d\n", (a*b) / i);break;}}system("pause");return 0;
}

法二(辗转相减法):

辗转相减法:不断地对两个数做减法,以此求出最大公约数。即用大数减小数,将所得结果保存到大数中;再用此时的大数减小数,将结果保存到大数中,如此重复,直到最后两数相等,便求出了最大公约数。

以求a = 24和b = 36的最大公约数为例,具体求解思路如下:

1. b=b-a=36-24=12;

2. a=a-b=24-12=12;

3.a=b = 12(此时两数相等) ---> 最大公约数为12

代码实现如下:

//辗转相减法求最大公约数,最小公倍数
int main()
{int a = 28, b = 40;int mul = a*b;while (a != b){if (a > b){a = a - b;}else if (a < b){b = b - a;}}printf("最大公约数为%d\n", a);printf("最小公倍数为%d\n", mul/a);system("pause");return 0;
}

法三(辗转相除法):

辗转相除法是求最大公约数的一种方法,其具体求解思路如下:

两数相除(不论大小),再用除数除以出现的余数(第一余数),再用第一余数除以出现的余数(第二余数),如此反复,直到最后余数是0为止,那么最后的除数便是这两个数的最大公约数。

以求24和50的最大公约数为例,具体求解步骤如下:

1.  24%50=24(余数不等于0)

2. 50%24=26(余数不等于0)

3. 24%26=24(余数不等于0)

4. 26%24=2(余数不等于0)

5.24%2=0(余数等于0) --->最大公约数为此时的除数2

代码实现如下:

#include <stdio.h>
#include <windows.h>
int main()
{int a = 24, b = 50;int tmp = 0;int mul = a*b;while (tmp = a%b){a = b;b = tmp;}printf("最大公约数为%d\n", b);printf("最小公倍数为%d\n", mul / b);system("pause");return 0;
}

 

 

 

这篇关于C语言求两个数的最大公约数、最小公倍数(三种方法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/948594

相关文章

java中BigDecimal里面的subtract函数介绍及实现方法

《java中BigDecimal里面的subtract函数介绍及实现方法》在Java中实现减法操作需要根据数据类型选择不同方法,主要分为数值型减法和字符串减法两种场景,本文给大家介绍java中BigD... 目录Java中BigDecimal里面的subtract函数的意思?一、数值型减法(高精度计算)1.

CentOS 7 YUM源配置错误的解决方法

《CentOS7YUM源配置错误的解决方法》在使用虚拟机安装CentOS7系统时,我们可能会遇到YUM源配置错误的问题,导致无法正常下载软件包,为了解决这个问题,我们可以替换YUM源... 目录一、备份原有的 YUM 源配置文件二、选择并配置新的 YUM 源三、清理旧的缓存并重建新的缓存四、验证 YUM 源

MySQL启动报错:InnoDB表空间丢失问题及解决方法

《MySQL启动报错:InnoDB表空间丢失问题及解决方法》在启动MySQL时,遇到了InnoDB:Tablespace5975wasnotfound,该错误表明MySQL在启动过程中无法找到指定的s... 目录mysql 启动报错:InnoDB 表空间丢失问题及解决方法错误分析解决方案1. 启用 inno

Python函数返回多个值的多种方法小结

《Python函数返回多个值的多种方法小结》在Python中,函数通常用于封装一段代码,使其可以重复调用,有时,我们希望一个函数能够返回多个值,Python提供了几种不同的方法来实现这一点,需要的朋友... 目录一、使用元组(Tuple):二、使用列表(list)三、使用字典(Dictionary)四、 使

Linux查看系统盘和SSD盘的容量、型号及挂载信息的方法

《Linux查看系统盘和SSD盘的容量、型号及挂载信息的方法》在Linux系统中,管理磁盘设备和分区是日常运维工作的重要部分,而lsblk命令是一个强大的工具,它用于列出系统中的块设备(blockde... 目录1. 查看所有磁盘的物理信息方法 1:使用 lsblk(推荐)方法 2:使用 fdisk -l(

使用Python获取JS加载的数据的多种实现方法

《使用Python获取JS加载的数据的多种实现方法》在当今的互联网时代,网页数据的动态加载已经成为一种常见的技术手段,许多现代网站通过JavaScript(JS)动态加载内容,这使得传统的静态网页爬取... 目录引言一、动态 网页与js加载数据的原理二、python爬取JS加载数据的方法(一)分析网络请求1

MySQL查看表的最后一个ID的常见方法

《MySQL查看表的最后一个ID的常见方法》在使用MySQL数据库时,我们经常会遇到需要查看表中最后一个id值的场景,无论是为了调试、数据分析还是其他用途,了解如何快速获取最后一个id都是非常实用的技... 目录背景介绍方法一:使用MAX()函数示例代码解释适用场景方法二:按id降序排序并取第一条示例代码解

Python中合并列表(list)的六种方法小结

《Python中合并列表(list)的六种方法小结》本文主要介绍了Python中合并列表(list)的六种方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋... 目录一、直接用 + 合并列表二、用 extend() js方法三、用 zip() 函数交叉合并四、用

Java 中的跨域问题解决方法

《Java中的跨域问题解决方法》跨域问题本质上是浏览器的一种安全机制,与Java本身无关,但Java后端开发者需要理解其来源以便正确解决,下面给大家介绍Java中的跨域问题解决方法,感兴趣的朋友一起... 目录1、Java 中跨域问题的来源1.1. 浏览器同源策略(Same-Origin Policy)1.

Java Stream.reduce()方法操作实际案例讲解

《JavaStream.reduce()方法操作实际案例讲解》reduce是JavaStreamAPI中的一个核心操作,用于将流中的元素组合起来产生单个结果,:本文主要介绍JavaStream.... 目录一、reduce的基本概念1. 什么是reduce操作2. reduce方法的三种形式二、reduce