求最大公约数和最小公倍数
最小 最大公约数 公倍数
2023-09-27 14:27:22 时间
非常easy的数学问题。只是大家是否可以准确实现?
求最大公约数(greatest common divisor)的方法:
一、辗转相除
①设有两个正整数i、j。 且i>j;
②计算c=i%j。
③若c等于0,则j是i和j的最大公约数;若c不等于0,则i=j。j=c。
④反复②③直到求得最大公约数;
二、相减法
①设有两正整数i、j。
②若i等于j,则i或j就是两数的最大公约数;
③若i>j,i=i-j ;否则,j=j-i。
④反复②③直到得到最大公约数
三、暴力枚举
①设有两正整数i、j。
②如果i<j,令k=i,
③i。j分别对k求余,若余数都为0,则k为i、j最大公约数;否则k--,继续运行③,直到求出两数最大公约数;
求最小公倍数(least common multiple)的方法:
一、暴力枚举
①设有正整数i,j。最好还是设i>j。
②令k=i;
③k分别对i。j求余,若余数均为零,则k为i。j的最小公倍数。否则令k+=i。反复③,直到求出最小公被数;
二、依据最大公约数和最小公倍数的关系求解
LCM(i,j) = i*j / GCD(i,j)。
两正整数的最小公倍数等于两数的积除以两数的最大公约数,最大公约数可以由前面的公式计算;
相关文章
- LeetCode 155. 最小栈
- EfficientDet框架详解 | 目前最高最快最小模型,可扩缩且高效的目标检测(附源码下载)...
- CentOS 7最小安装之后应该尽快做好的几件事情
- leetcode316场周赛 第三题 使数组相等的最小开销 (两数组一块排序)
- 使用机器人打印字典序最小的字符串(leetcode314周赛第三题)
- 最小 XOR leetcode第 313 场周赛 第三题
- HDU 1814 Peaceful Commission(2-sat 模板题输出最小字典序解决方式)
- C语言 求两数的最大公约数和最小公倍数
- 1344:【例4-4】最小花费
- 1231:最小新整数 2020-12-11
- JAVA求两个数的最小公倍数和最大公约数(两种方法)
- HDU -1151 二分匹配与有向无环图不相交最小路径覆盖数
- HDU 4606 Occupy Cities (计算几何+最短路+二分+最小路径覆盖)
- 最小二乘法
- poj3041-Asteroids , 二分图的最小顶点覆盖数 = 最大匹配数
- 数据结构与算法之最好学的最小生成树
- P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题
- 最大公约数和最小公倍数问题