大貓咪的新玩具C/C++ 語言：如何找最大公因數和最小公倍數
最大公因數和最小公倍數不常遇到
但還是紀錄一下，順便複習一下
最大公因數 (GCD)
GCD 是最大公因數，為 Greatest Common Divisor 的縮寫，也稱作 Highest Common Factor (HCF)，下面就展示兩種計算 GCD 的方法，其中以輾轉相除法的計算最為快速。
列舉法
我們直接使用窮舉的方法，從兩數中最小的數字開始檢查是否為兩數的公因數，如果不是答案的話，就將數字減一繼續檢查，到最後時都找不到的話，就直接回傳 1，因為 1 是任何整數的因數。
int gcd(int a, int b) {
int start = (a > b ? b : a);
for (int i = start; i > 1; --i) {
if ((a % i == 0) && (b % i == 0)) return i;
}
return 1;
}輾轉相除法
輾轉相除法又稱歐幾里得算法 (Euclidean algorithm)，是快速計算最大公因數的算法，詳細證明可以去 Wiki 觀看。
在計算過程中： 0. 假設我們有兩個數字 A 和 B，其中 A 較大。
- 我們會將較大的數 A 除以較小的數 B，並得到餘數 C。
- 之後我們用 B 取代 A，用 C 取代 B。
- 回到步驟 1，持續到 B 數值為 0，則答案為 A。
int gcd(int a, int b) {
if (a < b) {
int tmp = a;
a = b;
b = tmp;
}
if (b == 0) return a;
a = a % b;
return gcd(b, a);
}多個數字計算 GCD
如果今天數字超過兩個，要計算共同的 GCD 的話，我們可以採用以下性質：
$$ GCD(a,b,c) = GCD(GCD(a,b),c) $$
範例中的 gcd 上方介紹的 gcd。
#include <stdarg.h>
int GCD(int total, ...) {
va_list args;
va_start(args, total);
int val = va_arg(args, int);
for (int i = 1; i < total; i++) {
int number = va_arg(args, int);
val = gcd(val, number);
}
va_end(args);
return val;
}使用前要先傳入總共有幾個數字，下面的範例為傳入 3 個數字，分別為 12 18 63。
printf("GCD of 12, 18, 63 = %d\n", GCD(3, 12, 18, 63));最小公倍數 (LCM)
LCM 為最小公倍數，全名為 Least Common Multiple，一樣提供兩種方法。
列舉法
與 GCD 的列舉法類似，從兩數中最大的數字開始檢查是否為兩數的公倍數，如果不是答案的話，就將數字加一繼續檢查。
int lcm(int a, int b) {
int start = (a > b ? a : b);
for (int i = start;; ++i) {
if ((i % a == 0) && (i % b == 0)) return i;
}
}透過 GCD 求得
由於 LCM 和 GCD 有著以下的關係，因此我們可以透過 GCD 來計算 LCM，由於 LCM 一定為正整數，因此我們要加上絕對值，範例中的 gcd 為前段部分介紹的 gcd 的函式。
$$LCM(a,b) = \frac{|a \times b|}{GCD(a, b)}$$
#include <stdlib.h>
int lcm(int a, int b) {
return abs(a * b) / gcd(a, b);
}
C/C++ 語言中的數值運算陷阱：Integer Overflow and Underflow
有時候在做簡單加減乘除的時候，計算結果超出由於當前型態的範圍，而導致計算結果錯誤的問題，這邊簡單紀錄了幾個如何偵測這種問題的方法
閱讀全文
多個數字計算 LCM
如果今天數字超過兩個，要計算共同的 LCM 的話，我們可以採用以下性質：
$$ LCM(a,b,c) = LCM(LCM(a,b),c) $$
也就是說，先計算其中兩者的 LCM，再計算其結果和最後一者的 LCM，證明有興趣的可以到 Wiki 查看。
#include <stdarg.h>
int LCM(int total, ...) {
va_list args;
va_start(args, total);
int val = 1;
for (int i = 0; i < total; i++) {
int number = va_arg(args, int);
val = val * number / gcd(val, number);
}
va_end(args);
return val;
}一樣要記得確認是否有 Overflow。
printf("LCM of 7, 14, 10 = %d\n", LCM(3, 7, 14, 10));Reference
如果你覺得這篇文章有用 可以考慮贊助飲料給大貓咪