最大公因子

最大公因子

最大公因子又稱最大公約數(英語:greatest common divisor,gcd),指兩個或多個整數共同具有的最大約數

基本介紹

  • 中文名:最大公因子
  • 外文名:greatest common divisor
  • 又名:最大公約數
  • 定義:兩個或多個整數共同有的最大約數
  • 套用學科:數學
  • 相關術語:最低公倍數
定義,例子,程式代碼,

定義

最大公因子又稱最大公約數(英語:greatest common divisor,gcd),指兩個或多個整數共同具有的最大約數,記為
求兩個整數最大公約數主要的方法:
  • 窮舉法:分別列出兩整數的所有約數,並找出最大的公約數。
  • 素因數分解:分別列出兩數的素因數分解式,並計算共同項的乘積
  • 短除法:兩數除以其公同素因數,直到兩數互素時,所有除數的乘積即為最大公約數。
  • 輾轉相除法:兩數相除,取餘數重複進行相除,直到餘數為{\displaystyle 0}時,前一個除數即為最大公約數。
兩個整數{\displaystyle a,b}的最大公約數和最低公倍數(lcm)的關係為:
兩個整數的最大公約數可用於計算兩數的最低公倍數,或分數化簡成最簡分數
兩個整數的最大公約數和最低公倍數中存在分配律
直角坐標中,兩頂點為
的線段會通過
個格子點。

例子

54可以表示為兩兩不同正整數的乘積:
故54的正約數為
同樣地,24可以表示為:
故24的正約數為
24,54都有的正約數1,2,3,6即為公約數,其中最大的公約數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)

相關詞條

熱門詞條

聯絡我們