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

最大公因數

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

最大公因數(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# 最大公因數遞迴代码:

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

C++最大公因数递归代码:

template < typename T > T GCD(T a, T b)
{
	T ma = max(a, b);
	T mi = min(a, b);
	if (ma%mi != 0)
		return GCD(mi, (ma%mi));
	return mi;
}

C最大公因数递归代码:

/*请更改为您所需的类型*/int GCD(int a, int b)
{
	int ma = max(a, b);
	int mi = min(a, b);
	if (ma%mi != 0)
		return GCD(mi, (ma%mi));
	return mi;
}

外部链接[编辑]

参见[编辑]