最大公因數計算機

最大公因數計算機

成長中 AI Skill PRO

輸入計算

數學公式

gcd⁡(A,B)=gcd⁡(B,AmodB)\gcd\left(\text{A},\ \text{B}\right) = \gcd\left(\text{B},\ \text{A} \bmod \text{B}\right)
顯示計算步驟 (1)
  1. LCM(由GCD求得)

    lcm=|A|×|B|gcd⁡(A,B)\text{lcm} = \frac{\left|\text{A}\right| \times \left|\text{B}\right|}{\gcd\left(\text{A},\ \text{B}\right)}

    最小公倍數由最大公因數求得:兩數之乘積除以最大公因數。

使用統計

廣告

結果

最大公因數
12
GCD(48, 36)
GCD(最大公因數) 12
LCM(最小公倍數) 144

回報本頁錯誤

什麼是最大公因數?

兩個整數的最大公因數(GCD),在台灣的數學課本中也稱為「最大公約數」,英文又叫 highest common factor(HCF),指的是能同時整除這兩個數、且不留餘數的最大正整數。舉例來說,48 與 36 的最大公因數是 12,因為 12 是能同時整除這兩數的最大數字。這個最大公因數計算機會立刻算出答案,並一併顯示最小公倍數(LCM)。

兩個相互重疊的因數集合,中間醒目標示共有的因數
最大公因數是兩個數共有的最大因數。

如何使用這個計算機

在標示為 A 與 B 的欄位分別輸入兩個整數,結果就會自動呈現。工具會自動取每個輸入值的絕對值,因此就算輸入負數也能正確處理。如果其中一個數字輸入 0,最大公因數就會等於另一個數字(因為任何整數都能整除 0)。

輾轉相除法(歐幾里得演算法)解析

本計算機採用輾轉相除法,這是至今仍廣泛使用、歷史最悠久的演算法之一。它的原理很單純:\(\gcd(a, b) = \gcd(b, a \bmod b)\)。也就是不斷用兩數相除的餘數取代較大的數,直到餘數變成 0 為止;最後一個非零的除數就是最大公因數。這種做法不必先做質因數分解,即使面對極大的數字也能飛快算出結果。

廣告
流程圖迴圈,展示歐幾里得演算法不斷做除法並替換數值,直到餘數為零
歐幾里得演算法不斷用 \((b, a \bmod b)\) 替換 \((a, b)\),直到餘數為零。

實例演算

求 \(\gcd(48, 36)\):

$$48 \bmod 36 = 12 \rightarrow \gcd(36, 12)$$$$36 \bmod 12 = 0 \rightarrow \gcd(12, 0) = \mathbf{12}$$

接著計算最小公倍數:$$\frac{|48 \times 36|}{12} = \frac{1728}{12} = \mathbf{144}$$

常見問題

GCD 和 HCF 有什麼不同?完全沒有差別,兩者指的是同一個值,只是叫法不同。「greatest common divisor」在美國比較常見,「highest common factor」則常見於英國;在台灣我們通常稱為「最大公因數」或「最大公約數」。

兩個互質的數,最大公因數是多少?永遠是 1。像 8 和 15 這樣,除了 1 以外沒有任何共同的因數,這類數字就稱為互質(relatively prime)。

最大公因數會大於較小的那個數嗎?不會。最大公因數絕不會超過兩數中較小者;而當較小的數能整除較大的數時,最大公因數就剛好等於那個較小的數。

最後更新:

數學和統計熱門計算器

查看全部數學和統計計算器