本頁使用了標題或全文手工轉換

最大公因數

維基百科,自由的百科全書
前往: 導覽搜尋

最大公因數(Greatest Common Divisor,簡寫為G.C.D.;或Highest Common Factor,簡寫為H.C.F.),指某幾個整數共有因數中最大的一個。

求兩個整數最大公因數主要的方法:

  • 列舉法:各自列出因數,再找出最大的公因數。
  • 質因數分解法:兩數各作質因數分解,然後取出共有的項乘起來。
  • 短除法
  • 輾轉相除法擴展版):常使用於直觀上不容易判別公因數的場合。

兩個整數的最大公因數和最小公倍數(L.C.M.)的關係: G.C.D.(a, b) \times L.C.M.(a, b) = |ab|

兩個整數的最大公因數可用於計算兩數的最小公倍數,或分數化簡成最簡分數

兩個整數的最大公因數和最小公倍數中存在分配律

  • G.C.D.(a,\;L.C.M.(b, c)) = L.C.M.(G.C.D.(a, b)),\;G.C.D.(a,  c))
  • L.C.M.(a,\;G.C.D.(b, c)) = G.C.D.(L.C.M.(a, b)),\;L.C.M.(a,  c))

座標裏,將點(0, 0)和(a, b)連起來,通過整數座標的點的數目(除了(0, 0)一點之外)就是G.C.D.(a, b)。

例子[編輯]

54可以拆分為兩個不同的整數

 54 \times 1 = 27 \times 2 = 18 \times 3 = 9 \times 6. \,

54的因數有:

 1, 2, 3, 6, 9, 18, 27, 54. \,

同樣地,24的因數有:

 1, 2, 3, 4, 6, 8, 12, 24. \,

兩個列表內都有的數字為公因數:

 1, 2, 3, 6. \,

最大的數字是6。54和24的最大公因數是6。

 \gcd(54,24) = 6. \,

其他[編輯]

數字之間的最大公因數之所有因數是該組數字所有的公因數。

c# 最大公因數遞迴 Code:

       /// <summary>
       /// GCD最大公因數遞迴演算法
       /// </summary>
       private int GCD(int a, int b)
       {
           int max = Math.Max(a, b);
           int min = Math.Min(a, b);
           if (max%min!=0)
               return GCD(min, (max%min));
           return min;
       }

外部連結[編輯]

參見[編輯]