一、定義
C++最小公倍數是指兩個或多個整數的公共倍數中最小的那個數。例如，6和9的公倍數有18、27、36等，其中18是最小的，因此6和9的最小公倍數是18。
二、演算法原理
計算最小公倍數有多種演算法，其中最簡單的是枚舉法。給定兩個數a和b，首先計算它們的最大公約數，然後計算它們的積，最後將積除以最大公約數即為它們的最小公倍數。
int Gcd(int a, int b)
{
return b == 0 ? a : Gcd(b, a % b);
}
int Lcm(int a, int b)
{
return a / Gcd(a, b) * b;
}
三、代碼解釋
以上代碼實現了求兩個數的最小公倍數的函數Lcm，它調用了求最大公約數的函數Gcd。
在Gcd函數中，使用了三目運算符判斷b是否為0。如果b等於0，則返回a；否則，遞歸調用Gcd函數，將a%b作為新的b參數進行計算。
在Lcm函數中，先計算a和b的最大公約數，然後將a除以最大公約數乘以b，即為它們的最小公倍數。
四、改進演算法
以上代碼的時間複雜度為O(logn)，但是當a和b的差距非常大時，遞歸次數可能會很多。我們可以使用更高效的演算法來實現。
我們可以將a和b分解質因數，然後求出它們的公共質因子和非公共質因子，最後將它們相乘即可得到最小公倍數。
int Lcm(int a, int b)
{
int p = Gcd(a, b);
return a / p * b;
}
以上代碼實現了求兩個數的最小公倍數的函數Lcm，它調用了求最大公約數的函數Gcd。
在Lcm函數中，先計算a和b的最大公約數p，然後將a除以p乘以b，即為它們的最小公倍數。
五、結論
C++的最小公倍數演算法是一個基本的演算法，應用廣泛。對於兩個整數的最小公倍數，我們可以通過枚舉或者分解質因數的方式來計算。其中，分解質因數的演算法更加高效，在實際應用中更為常用。
原創文章，作者：FBBEB，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/366190.html
微信掃一掃 
支付寶掃一掃 