本页使用了标题或全文手工转换

最大公因數

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

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

兩個整數的最大公因數和最小公倍數(L.C.M.)的關係:

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

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

座標裏,將點(0, 0)和(a, b)連起來,通過整數座標的點的數目(除了(0, 0)一點之外)就是G.C.D.(a, b)。 大号文字==例子== 54可以拆分為兩個不同的整數

54的因數有:

同樣地,24的因數有:

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

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

程式代碼[编辑]

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

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

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;
}

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) {
	return a % b == 0 ? b : GCD(b, a % b);
}

Python[编辑]

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

外部链接[编辑]

参见[编辑]