《程序员数学:最小公倍数》—— stackoverflow.com 提问:“如何计算最小公倍数”?
作者:小傅哥 博客:https://bugstack.cn
源码:https://github.com/fuzhengwei/java-algorithms
❝沉淀、分享、成长,让自己和他人都能有所收获!? ❞
- 一、前言
- 二、用公约数实现
- 三、简单累加计算
- 四、表格推演计算
- 五、测试验证
- 六、常见面试
一、前言
在 stackoverflow.com 看到一道问题:计算两个整数的最小公倍数的最有效方法是什么?
乍一看,? 这能有啥。不就是计算下最小公倍数吗?但一想我脑袋中计算最小公倍数的方法;一种是在本子上通过短除法计算,另外一种是基于计算出的最大公约数,再使用公式:lcm(a, b) = |a * b| / gcd(a, b)
求得最小公倍数。—— 计算最大公约数是基于欧几里德算法(辗转相除法)
那么这样的计算方法是不是最有效的方法,另外如果是同时计算多个整数的最小公倍数,要怎么处理?
其实编程的学习往往就是这样,留心处处都是学问,你总是需要从各种细小的点中,积累自己的技术思维广度和纵向探索深度。好啦,接下来小傅哥就给大家介绍几种用于计算最小公倍数的算法。
二、用公约数实现
公式:lcm(a, b) = |a * b| / gcd(a, b)
public long lcm01(long m, long n) {
return ((m == 0) || (n == 0)) ? 0 : Math.abs(m * n) / gcd(m, n);
}
private long gcd(long m, long n) {
m = Math.abs(m);
n = Math.abs(n);
// 从一个数字中减去另一个数字,直到两个数字变得相同。
// 这将是 GCD。如果其中一个数字为零,也退出循环。
// https://en.wikipedia.org/wiki/Euclidean_algorithm
while (m != 0 && n != 0 && m != n) {
if (m > n) {
m = m - n;
} else {
n = n - m;
}
}
return m == 0 ? n : m;
}
- 首先这里是一个比较简单的方式,基于两数乘积除以最大公约数,得到的结果就是最小公倍数。
三、简单累加计算
此计算方式为,在一组正整数数列中,通过找到最小的数字进行自身累加循环,直至所有数字相同时,则这个数字为最小公倍数。—— 你能代码实现一下吗?
public long lcm02(long... n) {
long[] cache = n.clone();
// 以所有数字都相等作为条件
while (!isEquals(n)) {
System.out.println(JSON.toJSONString(n));
long min = n[0];
int idx = 0;
for (int i = 0; i < n.length; i++) {
if (min > n[i]) {
min = n[i];
idx = i;
}
}
n[idx] = cache[idx] + min;
}
return n[0];
}
- 在代码实现中,首先要把n个整数数列进行克隆保存。因为每次相加的都是最初的这个数列里的数字值。接下来就是以所有数字都相等作为条件循环判断,不断地的累加最小的数值即可。最终返回的就是最小公倍数。
四、表格推演计算
表格计算方式为将一组数字以最小的质数2开始整除,直到不能被2整除后,用下一个质数3继续整除(剩余的数字中比大的最小的质数)直至所有数字都为1的时候结束。最终所有有效的质数乘积就是最小公倍数。—— 想想如果这让你用代码实现,你能肝出来吗?
public long lcm03(long... n) {
Map<Long, List<Long>> keys = new HashMap<>();
for (long key : n) {
keys.put(key, new ArrayList<Long>() {{
add(key);
}});
}
System.out.print("执行表格计算:\r\nx ");
long primality = 2, cachePrimality = primality, filterCount = 0, lcm = 1;
// 以所有元素最后一位为1作为条件
while (filterCount != keys.size()) {
int refresh = 0;
filterCount = 0;
for (Map.Entry<Long, List<Long>> entry : keys.entrySet()) {
long value = entry.getValue().get(entry.getValue().size() - 1);
if (value == 1) {
filterCount++;
}
// 整除处理
if (value % primality == 0) {
entry.getValue().add(value / primality);
refresh++;
} else {
entry.getValue().add(value);
}
}
// 刷新除数
if (refresh == 0) {
for (Map.Entry<Long, List<Long>> entry : keys.entrySet()) {
long value = entry.getValue().get(entry.getValue().size() - 1);
// 找到下一个符合的素数
if (value > primality || (value < cachePrimality && value > primality)) {
cachePrimality = value;
}
entry.getValue().remove(entry.getValue().size() - 1);
}
primality = cachePrimality;
} else {
// 累计乘积
lcm *= cachePrimality;
System.out.print(cachePrimality + " ");
}
}
keys.forEach((key, values) -> {
System.out.println();
for (long v : values) {
System.out.print(v + " ");
}
});
System.out.println("\r\n");
return lcm;
}
- 在代码实现中我们通过 Map 作为表的key,Map 中的 List 作为表每一行数据。通过这样一个结构构建出一张表。
- 接下来以所有元素最后一位为1作为条件循环处理数据,用最开始的2作为素数整除列表中的数据,并保存到下一组数列中。当2不能整除时,则刷新素数,选取另外一个列表中最小的素数作为除数继续。
- 这个过程中会累计有效素数的乘积,这个乘积的最终结果就是最小公倍数。
五、测试验证
单元测试
@Test
public void test_euclidean() {
LastCommonMultiple lastCommonMultiple = new LastCommonMultiple();
// System.out.println("最小公倍数:" + lastCommonMultiple.lcm01(2, 7));
System.out.println("最小公倍数:" + lastCommonMultiple.lcm02(3, 4, 6));
// System.out.println("最小公倍数:" + lastCommonMultiple.lcm03(3, 4, 6));
System.out.println("最小公倍数:" + lastCommonMultiple.lcm03(3, 4, 6, 8));
//System.out.println("最小公倍数:" + lastCommonMultiple.lcm03(4, 7, 12, 21, 42));
}
测试结果
执行累加计算:
[3,4,6]
[6,4,6]
[6,8,6]
[9,8,6]
[9,8,12]
[9,12,12]
最小公倍数:12
执行表格计算:
x 2 2 2 3
3 3 3 3 1
4 2 1 1 1
6 3 3 3 1
8 4 2 1 1
最小公倍数:24
- 到这里测试就结束了,本章一共介绍了三种计算最小公倍数的方法。那如果只让你看到逻辑,你能写出最终的代码吗?
六、常见面试
- 如何计算两数的最小公倍数?
- 如果计算多个整数的最小公倍数?
- 你能说一下具体如何实现这种X的计算流程吗?
- 你知道最小公倍数计算的用途吗?
- What is the most efficient way to calculate the least common multiple of two integers?:https://stackoverflow.com/questions/3154454/what-is-the-most-efficient-way-to-calculate-the-least-common-multiple-of-two-int/3154503#3154503
- Least common multiple:https://en.wikipedia.org/wiki/Least_common_multiple
- Chebyshev function:https://en.wikipedia.org/wiki/Chebyshev_function
- END -
你好,我是小傅哥。一线互联网java
工程师、T8架构师,开发过交易&营销、写过运营&活动、设计过中间件也倒腾过中继器、IO板卡。不只是写Java语言,也搞过C#、PHP,是一个技术活跃的折腾者。
相关文章
- 技术生态两手抓,打造面向未来的企业级领先数据库
- 开发者必看,面试官心中的最佳数据库人才模型是什么样?
- 从相识到相惜:Redis与计算存储分离四部曲
- 面对key数量多和区间查询低效问题:Hash索引趴窝,LSM树申请出场
- 大数据处理黑科技:揭秘PB级数仓GaussDB(DWS) 并行计算技术
- 1秒启动Web Server
- 中心化交易所如何用Merkle Tree实现资产储备证明
- 揭秘GaussDB(for Redis):全面对比Codis
- 梦幻联动!金蝶&华为云面向大企业发布数据库联合解决方案
- 面对锁等待难题,数仓如何实现问题的秒级定位和分析
- 技术生态两手抓,打造面向未来的企业级领先数据库
- 看我如何连夜自建网站背刺我的求职对手们
- GaussDB拿下的安全认证CC EAL4+究竟有多难?
- 华为云开发者官网首页焕新升级,赋能开发者云上成长
- 从元宇宙、地产数字化到呼叫中心,华为云携手伙伴共创新价值
- 云享·人物丨造梦、探梦、筑梦,三位开发者在华为云上的寻梦之旅
- 华为云区块链三大核心技术国际标准立项通过
- 云小课|帮您高效快速上传组件至私有依赖库
- 一文详解GaussDB(DWS) 的并发管控和内存管控
- MemArts :高效解决存算分离架构中数据访问的组件