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

简介: 最大公因数和最小公倍数之间的性质:两个自然数的乘积等于这两个自然数的最大公约数和最小公倍数的乘积。最小公倍数的计算要把三个数的公有质因数和独有质因数都要找全,最后除到两两互质为止。

最小公倍数与最大公约数


  最小公倍数的性质:公倍数(common multiple)指在两个或两个以上的自然数中, 如果它们
  有相同的倍数,这些倍数就是它们的公倍数,其中除0以外最小的一个公倍数,  叫做这几
 个数的最小公倍数。
  最小公倍数特点:倍数的只有最小的没有最大,因为两个数的倍数可以无穷大。


最大公因数和最小公倍数之间的性质:两个自然数的乘积等于这两个自然数的最大公约数和最小公倍数的乘积。最小公倍数的计算要把三个数的公有质因数和独有质因数都要找全,最后除到两两互质为止。

求解最小公倍数的方法有 —直接暴力求解,另一种是—根据最大公约数和最小公倍数的关系来求解。


 暴力求解


两个数的最小公倍数肯定是两个数中值比较大的那一个,然后从较大值max一直递增,每递增一次,就拿max与n,和m进行取模,一旦max%n= =0和max%m= =0都成立那这个max就是最小公倍数啦。

第一种方法:思想就是找到既能整除a又能整除b的数m,这个数肯定是大于或等于a,b两个数的;那就先找出a,b中的最大值,然后给最大值每次自增循环取模a,b看能不能得0.先利用条件操作符算出最大值m。
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main()
{
  int n, m;
  scanf("%d%d", &n, &m);
  int max = (n > m ? n : m);//把最大值赋给max;
  while (max % n != 0 || max % m != 0)//max%n!=0或者max%m!=0时c肯定不是公倍数;继续找
  {
    max++;//只有当max%n==0和max%m==0同时满足才能跳出循环;
  }
  //跳出循环的max就是最小公倍数,因为max+1每次往上加一;
  printf("%d", max);
  return 0;
}


第二种方法,比第一种效率要高,利用m/a=整数原理(如果m是最小公倍数)。 最小公倍数一定是较大者的整数倍m/a = i(m是最小公倍数,那么i肯定也是整数中最小的)。那么 i*a%b==0这时就是最小公倍数。

int main()
{
  int a, b;
  scanf("%d%d", &a, &b);
  int i = 1;//i从1开始不能从0开始
  while ((i * a) % b != 0)
  {
    i++;//i*a 如果能取模b==0那么i*a肯定是a,b,的公倍数,因为i从小到达递增,
    //所以一开始的i就是最小公倍数;
  }
  printf("%d", i * a);
  return 0;
}


  根据关系求解:     最小公倍数=一个数/最大公约数


最小公约数可以根据辗转相除法来求解。

代码如下:


int main()
{
  int a, b, c;
  scanf("%d%d", &a, &b);
  int a1 = a;
  int b1 = b;
  while (c = a % b)//根据辗转相除法求最大公约数。
  {  
    c = a % b;
    a = b;
    b = c;
  }
  //最后b是最大公约数。注意!这里a b 的值已经变化,不能再使用了,所以
  //上面需要重新赋值给新的变量。
  printf("%d", a1*b1 / b);
  return 0;
}


当然还有许多方法可以求最大公约数啦也可以暴力求解。

以上只是萌新的想法,希望大家可以相互指教喔66a3aa7ce3da4e7faba7bbb285679762.png

相关文章
|
16小时前
|
云安全 人工智能 安全
AI被攻击怎么办?
阿里云提供 AI 全栈安全能力,其中对网络攻击的主动识别、智能阻断与快速响应构成其核心防线,依托原生安全防护为客户筑牢免疫屏障。
|
10天前
|
域名解析 人工智能
【实操攻略】手把手教学,免费领取.CN域名
即日起至2025年12月31日,购买万小智AI建站或云·企业官网,每单可免费领1个.CN域名首年!跟我了解领取攻略吧~
|
4天前
|
安全 Java Android开发
深度解析 Android 崩溃捕获原理及从崩溃到归因的闭环实践
崩溃堆栈全是 a.b.c?Native 错误查不到行号?本文详解 Android 崩溃采集全链路原理,教你如何把“天书”变“说明书”。RUM SDK 已支持一键接入。
420 189
|
2天前
|
数据采集 消息中间件 人工智能
跨系统数据搬运的全方位解析,包括定义、痛点、技术、方法及智能体解决方案
跨系统数据搬运打通企业数据孤岛,实现CRM、ERP等系统高效互通。伴随数字化转型,全球市场规模超150亿美元,中国年增速达30%。本文详解其定义、痛点、技术原理、主流方法及智能体新范式,结合实在Agent等案例,揭示从数据割裂到智能流通的实践路径,助力企业降本增效,释放数据价值。
|
8天前
|
人工智能 自然语言处理 安全
国内主流Agent工具功能全维度对比:从技术内核到场景落地,一篇读懂所有选择
2024年全球AI Agent市场规模达52.9亿美元,预计2030年将增长至471亿美元,亚太地区增速领先。国内Agent工具呈现“百花齐放”格局,涵盖政务、金融、电商等多场景。本文深入解析实在智能实在Agent等主流产品,在技术架构、任务规划、多模态交互、工具集成等方面进行全维度对比,结合市场反馈与行业趋势,为企业及个人用户提供科学选型指南,助力高效落地AI智能体应用。
|
4天前
|
消息中间件 安全 NoSQL
阿里云通过中国信通院首批安全可信中间件评估
近日,由中国信通院主办的 2025(第五届)数字化转型发展大会在京举行。会上,“阿里云应用服务器软件 AliEE”、“消息队列软件 RocketMQ”、“云数据库 Tair”三款产品成功通过中国信通院“安全可信中间件”系列评估,成为首批获此认证的中间件产品。此次评估覆盖安全可信要求、功能完备性、安全防护能力、性能表现、可靠性与可维护性等核心指标,标志着阿里云中间件产品在多架构适配与安全能力上达到行业领先水平。
313 194