求解最大公约数和最小公倍数

简介: 求解最大公约数和最小公倍数

求最大公约数


最大公约数的定义:如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数。几个自然数公有的约数,叫做这几个自然数的公约数。公约数中最大的一个公约数,称为这几个自然数的最大公约数。例: 在2、4、6中,2就是2,4,6的最大公约数。


 知道了最大公约数的定义后,我们来学习一下最大公约数的求解方法。


1.暴力求解法


 思路:假设有两个数m和n,先求出两个数中的较小值min,然后利用while循环找出m和n的最大公约数。while循环的循环体是如果m和n整除min同时为零,那么此时的min就是m和n的最大公约数;不符合该条件的话min自减一。


代码实现:


#include <stdio.h>
int main()
{
  int m, n;
  printf("请输入两个整数:>");
  scanf("%d %d", &m, &n);
  int min = (m < n ? m : n);
  while (1)
  {
    if ((m % min == 0) && (n % min == 0))
    {
      break;
    }
    min--;
  }
  printf("%d和%d的最大公约数是%d\n", m, n, min);
  return 0;
}


输出结果:

463a27e9676b4a11b71674ef3b4bd509.png


2. 辗转相除法


辗转相除法, 又名欧几里德算法(Euclidean algorithm),是求两个正整数之最大公约数的算法。它是已知最古老的算法, 其可追溯至公元前300年前。它的具体做法是:用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数。


代码实现:


#include <stdio.h>
int main()
{
  int m, n;
  printf("请输入两个整数:>");
  scanf("%d %d", &m, &n);
  int m1 = m;
  int n1 = n;//保存m和n的数据
  int r = 0;
  while (r = m % n)
  {
    m = n;
    n = r;
  }
  printf("%d和%d的最大公约数是%d\n", m1, n1, n);
  return 0;
}

d05003b32932475b81a04751a064dde8.png


输出结果:

6e789ebe18584b73bfd699d91871b016.png


求最小公倍数


  最小公倍数的定义:如果一个数既是a又是b的倍数,那么我们就把这个数叫着a和b的公倍数,如果这个数在a b的所有公倍数里为最小,那这个数就是最小公倍数。例如,10和20的最小公倍数是20。


1.暴力求解法


 假设有两个数m和n,先求出两个数中的最大值max,然后利用while循环找出m和n的最小公倍数。while循环的循环体是如果max整除m和n同时为零,那么此时的max就是m和n的最小公倍数;不符合该条件的话max自加一。


代码实现:


#include <stdio.h>
int main()
{
  int m, n;
  printf("请输入两个数:>");
  scanf("%d %d", &m, &n);
  int max = (m > n ? m : n);
  while (1)
  {
    if ((max % m == 0) && (max % n == 0))
    {
      break;
    }
        max++;
  }
  printf("%d和%d的最小公倍数是%d\n", m, n, max);
  return 0;
}


输出结果:

88b8b6514bb64ffdbafd2c1f99d66a93.png


2.最大公约数法


 假设有两个数m和n,且m和n的最大公约数为x、最小公倍数y,那么最小公倍数和最大公约数存在一个关系式:m * n = x * y。例如这个关系式,我们就可以实现我们的代码了。


代码实现:


#include <stdio.h>
int main()
{
  int m, n;
  printf("请输入两个数:>");
  scanf("%d %d", &m, &n);
  int m1 = m;
  int n1 = n;
  int r = 0;
  while (r = m % n)
  {
    m = n;
    n = r;
  }
  printf("%d和%d的最小公倍数是%d\n", m1, n1, m1 * n1 / n);
}


输出结果:


51cf46b7eb564273bc0aeb31d503406c.png


3.奇技淫巧


 因为最大公倍数肯定是其因素的整数倍,那么假设两个数为m和n,i等于1,其最小公倍数为k。如果m成i模除n为0,那么m*i就等于k,否则i++。


代码实现:


#include <stdio.h>
int main()
{
  int m, n;
  printf("请输入两个数:>");
  scanf("%d %d", &m, &n);
  int i = 1;
  while (m*i%n!=0)
  {
    i++;
  }
  printf("%d和%d的最小公倍数是%d\n", m, n, m*i);
  return 0;
}


输出结果:

003e3053e6c04fb9ad5ce03a6c81bed2.png


 本篇博客主要介绍了最大公约数和最小公倍数的几种常见方法。如果大家对其它的方法还感兴趣的话,可以自行查找,在这里就不在赘述了。最后,如果大家觉得有收获的话,大家可以点个赞支持一下!


结语


每个优秀的人都有一段沉默的时光,那段时光是付出了很多努力却得不到结果的日子,我们把它叫做扎根。




相关文章
资源块|带你读《5G空口特性与关键技术》之九
3GPP TS38.211 中对 Point A 进行了定义。需要说明的是,2018/6 版本的TS38.211-f20 中的定义在 2018/9 版本中没有变化,不过在2018/12 版本 TS38.211-f40 中,基于 RAN1#94b 会议的决议进行了修改,有关信息请参看 RAN1#94b会议报告以及提案 R1-1811817 和 R11810834。
13386 2
资源块|带你读《5G空口特性与关键技术》之九
|
Ubuntu Linux C语言
还在用Alpine作为你Docker的Python开发基础镜像?其实Ubuntu更好一点
一般情况下,当你想为你的Python开发环境选择一个基础镜像时,大多数人都会选择Alpine,为什么?因为它太小了,仅仅只有 5 MB 左右(对比 Ubuntu 系列镜像接近 100 MB),但事实的真相是,我们选择基础镜像并不是为了体验一下Python语法而已,在此基础上,我们需要调试和安装各种扩展,可能会安装很多三方依赖,甚至预设更多服务,在这种环境下,Alpine就并非是一个很好的选择了,本次我们就来分别在Alpine和Ubuntu上来体验一下安装和编译Python的区别。
还在用Alpine作为你Docker的Python开发基础镜像?其实Ubuntu更好一点
|
Web App开发 人工智能 安全
指南:Google Gemini 2.0 Pro国内版 (Gemini 2.0国内使用指南)
据称,谷歌 AI 推出的 Gemini Pro 国内版,是一款性能卓越的大型语言模型,其能力和表现均超越了广受欢迎的 ChatGPT。作为 Fostmar 的重大升级,它将为用户带来前所未有的 AI 交互体验
3586 0
|
SQL Oracle 关系型数据库
PLSQL查询Oracle表中文乱码解决
PLSQL查询Oracle表中文乱码解决
825 0
PLSQL查询Oracle表中文乱码解决
【异常】svn: E200009: Commit failed (details follow)/both sides of the move must be committed together的解决办法
svn: E200009: Commit failed (details follow)/both sides of the move must be committed together的解决办法
1458 0
【Shiro】7、Shiro实现控制用户并发登录并踢人下线(下)
在传统的项目中,同一账户是允许多人同时登录在线的,有的使用场景恰恰是不允许多人同时在线的,那么我们可以通过 Shiro 来控制并发登录,并实现后登录的用户,挤掉前面登录的用户
921 0
|
存储 监控 物联网
InfluxDB简介与场景
InfluxDB简介与场景
837 1
|
XML SQL Java
mybatis xml文件热加载实现
本文博主给大家带来一篇 mybatis xml 文件热加载的实现教程,自博主从事开发工作使用 Mybatis 以来,如果需要修改 xml 文件的内容,通常都需要重启项目,因为不重启的话,修改是不生效的,Mybatis 仅仅会在项目初始化的时候将 xml 文件加载进内存。
1124 1
mybatis xml文件热加载实现
|
SQL 消息中间件 缓存
阿里云大数据开发三面面经,已过,面试题已配答案
阿里云大数据开发三面面经,已过,面试题已配答案
1924 1
|
SQL 数据采集 存储
数据建设与治理丨Dataphin中如何进行Hologres开发
前言:在Dataphin 3.9中新增支持Hologres引擎的适配。Hologres是一站式实时数据仓库引擎,支持海量数据实时写入、实时更新、实时分析,支持标准SQL(兼容PostgreSQL协议),支持PB级数据多维分析(OLAP)与即席分析(Ad Hoc),支持高并发低延迟的在线数据服务(Serving)。通过Dataphin的研发平台能力以及数据资产治理能力,可提供更好的即席分析及实时数仓的构建能力。
1072 0
数据建设与治理丨Dataphin中如何进行Hologres开发