C++求兩個整數的最小公倍數(LCM)的方法

最小公倍數(LCM)是指能夠同時被兩個數整除的最小的正整數。在C++中，有幾種常見的方法可以計算兩個整數的最小公倍數。

方法一：利用最大公約數(GCD)計算

這是最常用且高效的方法，基于數學公式：

LCM(a, b) = (a × b) / GCD(a, b)

代碼實現

#include <iostream>
#include <algorithm> // 用于std::gcd (C++17及以上)// 計算GCD的函數（如果編譯器不支持C++17的std::gcd）
int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}int lcm(int a, int b) {// 防止乘法溢出，先除以GCDreturn (a / std::gcd(a, b)) * b;// 或者使用自定義的gcd函數：// return (a / gcd(a, b)) * b;
}int main() {int num1, num2;std::cout << "輸入兩個整數: ";std::cin >> num1 >> num2;std::cout << "LCM(" << num1 << ", " << num2 << ") = " << lcm(num1, num2) << std::endl;return 0;
}

方法二：逐次增加法

這種方法通過逐個測試較大的數的倍數，直到找到能被兩個數都整除的數。

代碼實現

#include <iostream>int lcm(int a, int b) {int max = (a > b) ? a : b;while (true) {if (max % a == 0 && max % b == 0) {return max;}++max;}
}int main() {int num1, num2;std::cout << "輸入兩個整數: ";std::cin >> num1 >> num2;std::cout << "LCM(" << num1 << ", " << num2 << ") = " << lcm(num1, num2) << std::endl;return 0;
}

方法三：質因數分解法

將兩個數分解質因數，然后取每個質因數的最高冪次相乘。

代碼實現

#include <iostream>
#include <map>// 質因數分解函數
std::map<int, int> primeFactors(int n) {std::map<int, int> factors;if (n == 0) return factors;// 處理2的因數while (n % 2 == 0) {factors[2]++;n /= 2;}// 處理奇數因數for (int i = 3; i * i <= n; i += 2) {while (n % i == 0) {factors[i]++;n /= i;}}// 如果剩下的n是質數if (n > 2) {factors[n]++;}return factors;
}int lcm(int a, int b) {if (a == 0 || b == 0) return 0;auto factorsA = primeFactors(a);auto factorsB = primeFactors(b);// 合并兩個質因數映射，取每個因數的最大指數for (const auto& pair : factorsB) {if (factorsA[pair.first] < pair.second) {factorsA[pair.first] = pair.second;}}// 計算LCMint result = 1;for (const auto& pair : factorsA) {for (int i = 0; i < pair.second; ++i) {result *= pair.first;}}return result;
}int main() {int num1, num2;std::cout << "輸入兩個整數: ";std::cin >> num1 >> num2;std::cout << "LCM(" << num1 << ", " << num2 << ") = " << lcm(num1, num2) << std::endl;return 0;
}

方法比較

1. GCD方法：最有效，時間復雜度為O(log(min(a, b)))，推薦使用。
2. 逐次增加法：簡單但效率低，時間復雜度為O(max(a, b))，僅適用于小數字。
3. 質因數分解法：理論上有用，但實現復雜且效率不如GCD方法，適用于需要質因數分解的場景。

處理大數和特殊情況

在實際應用中，還需要考慮：

• 處理負數（LCM總是正數）
• 處理零（任何數與零的LCM是零）
• 防止整數溢出

改進版GCD方法實現

#include <iostream>
#include <algorithm> // 用于std::gcd
#include <cstdlib>   // 用于absint lcm(int a, int b) {if (a == 0 || b == 0) return 0;// 取絕對值a = std::abs(a);b = std::abs(b);// 防止溢出，先除以GCD再相乘return (a / std::gcd(a, b)) * b;
}int main() {int num1, num2;std::cout << "輸入兩個整數: ";std::cin >> num1 >> num2;std::cout << "LCM(" << num1 << ", " << num2 << ") = " << lcm(num1, num2) << std::endl;return 0;
}

這種方法是最推薦的，因為它高效、簡潔且能處理各種邊界情況。