计算两个整数的最小公倍数最有效的方法是什么？
我刚刚想出这个，但它确实还有一些不足之处。
int n=7, m=4, n1=n, m1=m;
while( m1 != n1 ){
if( m1 > n1 )
n1 += n;
else
m1 += m;
}
System.out.println( "lcm is " + m1 );
ablcm(a, b) = ab/gcd(a,b)那么，问题就变成了，如何找到gcd？ 欧几里得算法通常是计算 gcd 的方法。经典算法的直接实现是高效的，但是有一些变体利用二进制算术来做得更好一些。请参阅 Knuth 的“计算机编程艺术”第 2 卷，“半数值算法”§ 4.5.2。
记住 最小公倍数是两个或多个数字中每个数字的倍数的最小整数。
如果您想计算三个整数的最小公倍数，请按照以下步骤操作：
**Find the LCM of 19, 21, and 42.**
写出每个数字的质因数分解。 19 是质数。您不需要因式分解 19。
21 = 3 × 7
42 = 2 × 3 × 7
19
将每个质因数重复出现在上述任何质因数分解中的最大次数。
2×3×7×19=798
21、42、19 的最小公倍数是 798。
下面 C++ 中的最佳解决方案，不会溢出
#include <iostream>
#include <tuple>
long long gcd(long long a, long long b) {
while (b != 0)
std::tie(a, b) = std::make_tuple(b, a % b);
return a;
}
long long lcm(long long a, long long b) {
if (a > b)
return (a / gcd(a, b)) * b;
else
return (b / gcd(a, b)) * a;
}
int main() {
long long int a, b;
std::cin >> a >> b;
std::cout << lcm(a, b) << std::endl;
return 0;
}
扩展@John D. Cook答案，这也是该问题的标记答案。 (https://stackoverflow.com/a/3154503/13272795)，我正在分享寻找n个数字的最小公倍数的算法，它可能是2个数字或任何数字的最小公倍数。此代码的来源是this
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Returns LCM of array elements
ll findlcm(int arr[], int n)
{
// Initialize result
ll ans = arr[0];
// ans contains LCM of arr[0], ..arr[i]
// after i'th iteration,
for (int i = 1; i < n; i++)
ans = arr[i] * ans/gcd(arr[i], ans);
return ans;
}
我不知道它是否已优化，但可能是最简单的：
public void lcm(int a, int b)
{
if (a > b)
{
min = b;
max = a;
}
else
{
min = a;
max = b;
}
for (i = 1; i < max; i++)
{
if ((min*i)%max == 0)
{
res = min*i;
break;
}
}
Console.Write("{0}", res);
}
这是在 python 中查找两个数字的 LCM 的高效方法。
def gcd(a, b):
if min(a, b) == 0:
return max(a, b)
a_1 = max(a, b) % min(a, b)
return gcd(a_1, min(a, b))
def lcm(a, b):
return (a * b) // gcd(a, b)
使用欧几里得算法求 gcd，然后计算 a 除以 gcd 和 b 的乘积的 lcm，对我来说很有效。
int euclidgcd(int a, int b){
if(b==0)
return a;
int a_rem = a % b;
return euclidgcd(b, a_rem);
}
long long lcm(int a, int b) {
int gcd=euclidgcd(a, b);
return (a/gcd*b);
}
int main() {
int a, b;
std::cin >> a >> b;
std::cout << lcm(a, b) << std::endl;
return 0;
}
连续取两个数中较大者的倍数，直到结果是较小者的倍数。
这可能有用..
public int LCM(int x, int y)
{
int larger = x>y? x: y,
smaller = x>y? y: x,
candidate = larger ;
while (candidate % smaller != 0) candidate += larger ;
return candidate;
}
C++ 模板。编译时间
#include <iostream>
const int lhs = 8, rhs = 12;
template<int n, int mod_lhs=n % lhs, int mod_rhs=n % rhs> struct calc {
calc() { }
};
template<int n> struct calc<n, 0, 0> {
calc() { std::cout << n << std::endl; }
};
template<int n, int mod_rhs> struct calc<n, 0, mod_rhs> {
calc() { }
};
template<int n, int mod_lhs> struct calc <n, mod_lhs, 0> {
calc() { }
};
template<int n> struct lcm {
lcm() {
lcm<n-1>();
calc<n>();
}
};
template<> struct lcm<0> {
lcm() {}
};
int main() {
lcm<lhs * rhs>();
}
2 个数字的乘积等于 LCM * GCD 或 HCF。所以求 LCM 的最好方法就是求 GCD 并用 GCD 划分乘积。即 LCM(a,b) = (a*b)/GCD(a,b)。
首先你要找到最大公约数
for(int i=1; i<=a && i<=b; i++) {
if (i % a == 0 && i % b == 0)
{
gcd = i;
}
}
之后，使用 GCD 你可以轻松找到最小公倍数，就像这样
lcm = a / gcd * b;
从 Python 3.8 开始，数学库中添加了
lcm()math.lcm(*integers)
返回指定整数参数的最小公倍数。如果所有参数均非零，则返回值是所有参数的倍数的最小正整数。如果任何参数为零，则返回值为 0。不带参数的 lcm() 返回 1。
因为我们知道数学性质，即 “任意两个数字的 LCM 和 HCF 的乘积等于这两个数字的乘积”。
假设 X 和 Y 是两个整数， 然后 X * Y = HCF(X, Y) * LCM(X, Y)
现在我们可以通过知道HCF来找到LCM，我们可以通过欧几里德算法找到HCF。
LCM(X, Y) = (X * Y) / HCF(X, Y)
希望这会很有效率。
import java.util.*;
public class Hello {
public static int HCF(int X, int Y){
if(X == 0)return Y;
return HCF(Y%X, X);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int X = scanner.nextInt(), Y = scanner.nextInt();
System.out.print((X * Y) / HCF(X, Y));
}
}
是的，计算 LCM 的方法有很多种，例如使用 GCD (HCF)。 您可以应用素数分解，例如（优化/朴素）Sieve Eratosthenes 或查找素数因子来计算 GCD，这比直接计算 LCM 快得多。那么如上所述，LCM(X, Y) = (X * Y) / GCD(X, Y)
我用谷歌搜索了同样的问题，并找到了这个 Stackoverflow 页面， 不过我用 python 提出了另一个简单的解决方案
def find_lcm(numbers):
h = max(numbers)
lcm = h
def check(l, numbers):
remainders = [ l%n==0 for n in numbers]
return all(remainders)
while (check(lcm, numbers) == False):
lcm = lcm + h
return lcm
对于
numbers = [120,150,135,225]5400numbers = [120,150,135,225]
print(find_lcm(numbers)) # will print 5400
欧几里得 GCD 代码片段
int findGCD(int a, int b) {
if(a < 0 || b < 0)
return -1;
if (a == 0)
return b;
else if (b == 0)
return a;
else
return findGCD(b, a % b);
}