作者:小傅哥 博客: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];
}
表格计算方式为将一组数字以最小的质数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;
}
单元测试
@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
- END -
你好,我是小傅哥。一线互联网java
工程师、T8架构师,开发过交易&营销、写过运营&活动、设计过中间件也倒腾过中继器、IO板卡。不只是写Java语言,也搞过C#、PHP,是一个技术活跃的折腾者。