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

最大公因數

維基百科,自由的百科全書
跳至導覽 跳至搜尋

數學中,兩個或多個整數最大公因數英語:greatest common factorhcf)指能夠整除這些整數的最大正整數(這些整數不能都為零)。例如8和12的最大公因數為4。最大公因數也稱最大公因數英語:greatest common divisorgcd)。

整數序列的最大公因數可以記為

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

  • 窮舉法:分別列出兩整數的所有因數,並找出最大的公因數。
  • 質因數分解:分別列出兩數的質因數分解式,並計算共同項的乘積
  • 短除法:兩數除以其共同質因數,直到兩數互質時,所有除數的乘積即為最大公因數。
  • 輾轉相除法:兩數相除,取餘數重複進行相除,直到餘數為時,前一個除數即為最大公因數。

兩個整數的最大公因數和最小公倍數lcm)的關係為:

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

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

直角坐標中,兩頂點為的線段會通過格子點

概述[編輯]

例子[編輯]

54和24的最大公因數是多少?

數字54可以表示為幾組不同正整數的乘積:

故54的正因數為

同樣地,24可以表示為:

故24的正因數為

這兩組數列中的共同元素即為54和24的公因數

其中的最大數6即為54和24的最大公因數,記為:

互質數[編輯]

如果兩數的最大公因數為1,那麼這兩個數互質。例如,9和28就是互質數。

幾何角度的說明[編輯]

"瘦長的矩形區域,劃分成了正方形的網格,寬兩格、高五格。"
24乘60的矩形被十個12乘12的正方形格子完全覆蓋,即12為24和60的最大公因數。推而廣之,如果cab的最大公因數,那麼ab的矩形就可以被若干個邊長為c的正方形格子完全覆蓋。

假設有一個大小為24乘60的矩形區域,這個區域可以按照不同的大小劃分正方形網格:1乘1、2乘2、3乘3、4乘4、6乘6、12乘12。因此,12是24和60的最大公因數。大小為24乘60的矩形區域,可以按照12乘12的大小劃分正方形網格,一邊有兩格(24/12 = 2)、另一邊有五格(60/12 = 5)。

計算[編輯]

質因數分解法[編輯]

可以通過質因數分解來計算最大公因數。例如計算,可以先進行質因數分解 ,因為其中表達式的「重合」,所以。實踐中,這種方法只在數字比較小時才可行,因為對較大數進行質因數分解通常會耗費大量的時間。

再舉一個用文氏圖表示的例子,計算48和180的最大公因數。首先對這兩個數進行質因數分解:

48 = 2 × 2 × 2 × 2 × 3
180 = 2 × 2 × 3 × 3 × 5

它們之中的共同元素是兩個2和一個3:

Least common multiple.svg[1]
最小公倍數 = 2 × 2 × ( 2 × 2 × 3 ) × 3 × 5 = 720
最大公因數 = 2 × 2 × 3 = 12

輾轉相除法[編輯]

相比質因數分解法,輾轉相除法的效率更高。

計算時,先將48除以18得到2、餘數12,然後再將18除以12得到商1、餘數6,再將12除以6得到商2、餘數0,即得到最大公因數6。我們只關心每次除法的餘數是否為0,為0即表示得到答案。這一算法更正式的描述是這樣的:

其中

如果參數都大於0,那麼該算法可以寫成更簡單的形式:

,
如果 a > b
如果 b > a
使用輾轉相除法計算62和36的最大公因數2的演示動畫。

性質[編輯]

  • 任意ab的公因數都是因數
  • 函數滿足交換律
  • 函數滿足結合律

程式代碼[編輯]

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

以下使用輾轉相除法實現。

C#[編輯]

1 private int GCD(int a, int b) {
2 	if(0 != b) while(0 != (a %= b) && 0 != (b %= a));
3 	return a + b;
4 }

C++[編輯]

運行時計算實現:

template < typename T >
T GCD(T a, T b) {
	if(b) while((a %= b) && (b %= a));
	return a + b;
}

編譯時計算實現:

#include <iostream>
#include <type_traits>

template<typename T, std::enable_if_t<std::is_integral<T>::value, T> a, std::enable_if_t<std::is_integral<T>::value, T> b>
struct HCF{
public:
    static const T value=HCF<T, (a>b? b: a), (a>b? a%b: b%a)>::value;
};
template<typename T, std::enable_if_t<std::is_integral<T>::value, T> a>
struct HCF<T, a, 0>{
public:
    static const T value=a;
};
int main(){
    std::wcout<<HCF<int, 12, 64>::value<<std::endl;//Output: 4
}

C[編輯]

int GCD(int a, int b)
{
	if (b)
            while((a %= b) && (b %= a))
                ;
	return a + b;
}

Java[編輯]

private int GCD(int a, int b) {
        if(b==0) return a; 
	return a % b == 0 ? b : GCD(b, a % b);
}

Python[編輯]

GCD = lambda a, b: (GCD(b, a % b) if a % b else b)

參考文獻[編輯]

外部連結[編輯]

參見[編輯]