求最大公约数和最小公倍数的算法

简介: 求最大公约数和最小公倍数的算法

理论部分(辗转相除法)

 

代码部分

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
//求最大公约数
int gcd(int a, int b)
{
  int temp;
  while (b > 0)
  {
    temp = a % b;//创建一个变量存储a%b的余数
    a = b;//根据算法逻辑,用上一个式子的除数作下一个式子的被除数(所以a=b),上一个式子的余数作为下一个式子的除数(b=temp),直到余数为0;
    b = temp;
  }
  return a;//最后一定是返回除数
}
int lcm(int a, int b)
{
  return (a * b) / gcd(a, b);//利用公式   ab的乘积除以他们的最大公约数得到的结果为最小公倍数
}
int main()
{
  int a, b;
  printf("请输入两个正整数:\n");
  scanf("%d %d", &a, &b);
  int max = gcd(a, b);
  int min = lcm(a, b);
  printf("最大公约数为:%d\n", max);
  printf("最小公倍数为:%d\n", min);
  return 0;
}

暴力枚举法

/*枚举法:从1开始,直到i能够把a,b全部整除*/
int main()
{
  int a = 0;
  int b = 0;
  int i = 1;
  scanf("%d %d", &a, &b);
  while (i % a != 0 || i % b != 0)
  {
    i++;
  }
  printf("%d", i);
}
/*乘法枚举*/
int main()
{
    long long int a = 0;
    long long int b = 0;
    int i = 1;
    scanf("%d%d",&a,&b);
    while (a * i % b)
    {
      i++;
    }
    printf("%lld", a*i);
}

希望能对读者有所帮助!

目录
打赏
0
0
0
0
2
分享
相关文章
|
9月前
|
Python欧几里得算法找最大公约数
Python欧几里得算法找最大公约数
95 0
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-2 算法训练 最大最小公倍数
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-2 算法训练 最大最小公倍数
57 0
算法训练之最大最小公倍数 ALGO002
算法训练之最大最小公倍数 ALGO002
82 0
转:最大公约数算法很无聊吗?一个轻松方法(辗转相除法)3行代码搞定
最大公约数算法不是很无聊,计算最大公约数是数学中一个重要的概念,可以用于判断两个数是否互质、求分数的约分等,在很多领域都有广泛的应用。辗转相除法3行代码搞定。
88 0
每日算法系列【LeetCode 1363】形成三的最大倍数
每日算法系列【LeetCode 1363】形成三的最大倍数
107 0
基于GRU网络的MQAM调制信号检测算法matlab仿真,对比LSTM
本研究基于MATLAB 2022a,使用GRU网络对QAM调制信号进行检测。QAM是一种高效调制技术,广泛应用于现代通信系统。传统方法在复杂环境下性能下降,而GRU通过门控机制有效提取时间序列特征,实现16QAM、32QAM、64QAM、128QAM的准确检测。仿真结果显示,GRU在低SNR下表现优异,且训练速度快,参数少。核心程序包括模型预测、误检率和漏检率计算,并绘制准确率图。
77 65
基于GRU网络的MQAM调制信号检测算法matlab仿真,对比LSTM
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等