GCD & LCM
GCD 是將所有輸入均勻地劃分的最大數字。 LCM 是所有輸入均勻分成的最小數字。
GCD
—
最大的公約數
LCM
—
最不常見的倍數
演算法
GCD 使用 Euclid 演算法（約 300 BC — 仍在使用的最古老的演算法之一）：
GCD(a, b):
while b ≠ 0:
a, b = b, a mod b
return a
LCM 源自 GCD：
LCM(a, b) = |a × b| / GCD(a, b)
對於兩個以上的數字，成對應用：GCD(a, b, c) = GCD(GCD(a, b), c)。
例子
| 號碼 | GCD | LCM |
|---|---|---|
| 12, 18 | 6 | 36 |
| 4, 6 | 2 | 12 |
| 7, 13 | 1 | 91 |
| 12, 18, 24 | 6 | 72 |
參考文獻
- Greatest common divisor and the Euclidean algorithmWikipedia · en.wikipedia.org
- Least common multiple (lcm(a,b) = |ab|/gcd(a,b))Wikipedia · en.wikipedia.org
常見問題
什麼是GCD？
GCD（最大的公約數），也稱為 GCF（最大公因數）或 HCF（最高公因數），是最大的正整數，它不剩餘地除以所有給定的數字。 GCD(12, 18) = 6，因為 6 是將 12 和 18 都分開的最大數字。
什麼是LCM？
LCM（最小公倍數）是最小的正整數，可以被所有給定的數字整除。 LCM(4, 6) = 12，因為 12 是 4 和 6 均勻分成的最小數字。
GCD 是如何計算的？
計算器使用 Euclid 演算法：GCD(A, B) = GCD(B, A MOD B)，重複直到 B = 0。然後透過成對應用 GCD 來減少多個數字。
GCD和LCM有什麼關係？
對於兩個數字 A 和 B： LCM(A, B) = |A × B| / GCD(a, b)。 這就是為什麼首先減少 GCD 可以防止溢位。
如何分享我的計算？
單擊“與我的數字共享”以複製與您的輸入一起重新開啟的 URL。
嵌入這個計算器
將此免費計算器新增到您自己的網站。 複製片段 - 它適用於您可以貼上 HTML 並與此頁面保持同步的任何地方。