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

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

对于求解这两道道例题有很多种不同的解法,比如辗转相除法,穷举法,等等,这次简单介绍一下。


最大公约数


1.辗转相除法


辗转相除法, 又名欧几里德算法(Euclidean algorithm。 它的具体做法是:用较小数除较大数,再用出现的余数(第一个余数)去除除数,再用出现的余数(第二个余数)去除第一个余数,如此反复,直到最后余数是0为止。


代码如下:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int eual(int a, int b) {
  int t;
  while (b != 0) {
    t = a % b;
    a = b;
    b = t;
  }
  return a;
}
int main() {
  int a, b;
  scanf("%d%d", &a, &b);
  printf("eual=%d\n", eual(a, b));
  return 0;
}

2.穷举法


由于a和b的最大公约数不可能比a和b中的较小者还大,否则一定不能整除它,因此,先找到a和b中的较小者min,然后从min开始逐次减1尝试每种可能,即检验min到1之间的所有整数,第一个满足公约条件的min,就是a和b的最大公约数。

代码如下

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main()
{
    int a, b, min;
    scanf("%d %d", &a, &b);
    min = a < b ? a : b;
    while (!(a % min == 0 && b % min == 0))
    {
        min--;
    }
    printf("%d", min);
    return 0;
}


求最小公倍数


1.穷举法


m和n的最小公倍数一定比m和n大,也就是说要>= m,n的较大值

找到这个最大值,并且不断的++,总能找到一个值能够同时整除m和n

代码如下


#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main()
{
    int m, n, k;
    scanf("%d %d", &m, &n);
    k = m > n ? m : n;
    for (k;; k++)
    {
        if (k % m == 0 && k % n == 0)
            break;
    }
    printf("%d", k);
    return 0;
}

2.改良版的穷举法


代码如下:


#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main()
{
    int m, n;
    scanf("%d %d", &m, &n);
    int i=1;
    while(m*i % n !=0)
    {
        i++
    }
    printf("%d", m*i);
    return 0;
}


相关文章
|
8月前
|
算法
求最大公约数和最小公倍数的算法
求最大公约数和最小公倍数的算法
94 0
|
8月前
|
人工智能 算法 C++
c++算法学习笔记 (18) 约数
c++算法学习笔记 (18) 约数
|
8月前
|
算法 Python
Python欧几里得算法找最大公约数
Python欧几里得算法找最大公约数
93 0
|
8月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-2 算法训练 最大最小公倍数
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-2 算法训练 最大最小公倍数
55 0
|
8月前
|
算法 Python
最大公约数算法
最大公约数算法
|
8月前
|
算法 Python
最小公倍数算法
最小公倍数算法
|
算法
算法训练之最大最小公倍数 ALGO002
算法训练之最大最小公倍数 ALGO002
65 0
|
算法 Python
转:最大公约数算法很无聊吗?一个轻松方法(辗转相除法)3行代码搞定
最大公约数算法不是很无聊,计算最大公约数是数学中一个重要的概念,可以用于判断两个数是否互质、求分数的约分等,在很多领域都有广泛的应用。辗转相除法3行代码搞定。
79 0
|
15天前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
|
15天前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
109 68