计算两个整数的最小公倍数的最有效方法是什么？
计算两个整数的最小公倍数的最有效方法是什么？
我只是想出了这个，但肯定会留下一些不尽人意的地方。
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 ); a和b最小公倍数（lcm）是它们的乘积除以它们的最大公约数（gcd）（即lcm(a, b) = ab/gcd(a,b) ）。
那么，问题就变成了，如何findgcd？ 欧几里得algorithm一般是如何计算gcd的。 经典algorithm的直接实现是有效的，但是有一些变体可以利用二进制algorithm做得更好一些。 参见Knuth的“ 计算机程序devise艺术 ” 第2卷，“算术algorithm”第4.5.2节 。
记住最小公倍数是两个或多个数字中每一个的倍数的最小整数。
如果您正在试图找出三个整数的LCM，请按照下列步骤操作：
**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。
我认为“ 最大的共同分裂减less ”的做法应该会更快。 首先计算GCD（例如使用Euclidalgorithm ），然后用GCD除以两个数的乘积。
首先，你必须find最大的约数
for(int = 1; i <= a && i <= b; i++) { if (i % a == 0 && i % b == 0) { gcm = i; } }
之后，使用GCM，您可以轻松find像这样的最小公倍数
lcm = a / gcm * b;
我不知道它是否优化，但可能是最简单的：
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); }
取两个数中较大者的连续倍数，直到结果是较小的倍数。
这可能工作..
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 ++中最好的解决scheme没有溢出
#include <iostream> using namespace std; long long gcd(long long int a, long long int b){ if(b==0) return a; return gcd(b,a%b); } 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 ; cin>>a>>b; cout<<lcm(a,b)<<endl; return 0; }
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>(); }
