最小公倍數 (LCM) = |a*b| / 最大公約數 (GCD)
核心算法：輾轉相除法 (歐幾里得算法)
// 遞歸版
int gcd_recursive(int a, int b) {
return b == 0 ? a : gcd_recursive(b, a % b);
}
// 迭代版 (推薦，無棧溢出)
int gcd_iterative(int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
完整程序（含溢出保護）
#include <stdio.h>
#include <stdlib.h> // llabs
long long gcd(long long a, long long b) {
a = llabs(a); b = llabs(b);
while (b) { long long r = a % b; a = b; b = r; }
return a;
}
// LCM 可能溢出 int，用 long long 並先除後乘
long long lcm(long long a, long long b) {
if (a == 0 || b == 0) return 0;
long long g = gcd(a, b);
return llabs(a / g * b); // 先除後乘，減小中間值溢出風險
}
int main() {
long long m, n;
printf("輸入兩個正整數: ");
if (scanf("%lld %lld", &m, &n) != 2 || m <= 0 || n <= 0) {
printf("輸入無效\n"); return 1;
}
printf("最大公約數: %lld\n", gcd(m, n));
printf("最小公倍數: %lld\n", lcm(m, n));
return 0;
}
關鍵點總結
- 輾轉相除法：時間複雜度 O(log min(a,b))，極快。
- 先除後乘：
a / gcd * b 避免 a*b 直接溢出。
- 處理負數/零：取絕對值；零的 LCM 定義為 0。
- 大整數：超出 64 位需用 GMP 庫或手工高精度乘除。
擴展：多數 LCM
long long lcm_array(long long *arr, int n) {
long long res = arr[0];
for (int i = 1; i < n; ++i) res = lcm(res, arr[i]);
return res;
}
