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

最大公因數

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

最大公因數英語: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;
}

編譯時計算實現:

#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)

外部連結[編輯]

參見[編輯]