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

最大公因數

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

最大公因數英语:greatest common divisorgcd),指兩個或多個整數共同具有的最大因數,記為

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

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

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

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

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

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

例子[编辑]

可以表示為兩兩不同正整數的乘積:

的正因數為

同樣地,可以表示為:

的正因數為

都有的正因數即為公因數,其中最大的公因數即為最大公因數,記為

程式代碼[编辑]

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

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

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)

外部链接[编辑]

参见[编辑]