[解決済み] 2つの整数の最小公倍数を計算する最も効率的な方法は何でしょうか？

質問

2つの整数の最小公倍数を計算する最も効率的な方法は何でしょうか？

今思いついたのですが、確かに何か物足りないですね。

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 );

解決方法は？

の最小公倍数(lcm)は a と b はそれらの積を最大公約数(gcd)で割ったものです(例) lcm(a, b) = ab/gcd(a,b) ).

そこで、gcdをどのように求めるかが問題になります。 は、次のようになる。 ユークリッド・アルゴリズム は一般的にgcdを計算する方法です。 古典的なアルゴリズムの直接実装は効率的ですが、二項演算を利用してもう少しうまくやるバリエーションもあります。 以下を参照してください。 クヌース の「"」。 コンピュータ・プログラミングの技術 " 第2巻、quot;半数アルゴリズム" § 4.5.2 .