njtynhj

最大公因數（英语：highest common factor，hcf）也稱最大公約數（英语：greatest common divisor，gcd）是數學詞彙，指能够整除多個整數的最大正整数。而多個整数不能都为零。例如8和12的最大公因数为4。

整数序列 $a$ 的最大公因数可以記為 $displaystyle (a_1,a_2,dots ,a_n)$ 或 $displaystyle gcd(a_1,a_2,dots ,a_n)$ 。

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

窮舉法：分別列出兩整數的所有因數，並找出最大的公因數。

質因數分解：分別列出兩數的質因數分解式，並計算共同項的乘積。

短除法：兩數除以其共同質因數，直到兩數互質時，所有除數的乘積即為最大公因數。

輾轉相除法：兩數相除，取餘數重複進行相除，直到餘數為 $displaystyle 0$ 時，前一個除數即為最大公因數。

兩個整數 $a, b$ 的最大公因數和最小公倍數（lcm）的關係為：

\text{[math]}

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

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

displaystyle gcd(a,operatorname lcm (b,c))=operatorname lcm (gcd(a,b),gcd(a,c))

displaystyle operatorname lcm (a,gcd(b,c))=gcd(operatorname lcm (a,b),operatorname lcm (a,c))

在直角坐標中，兩頂點為 $displaystyle (0,0),(a,b)$ 的線段會通過 $displaystyle gcd(a,b)+1$ 個格子點。

概述

例子

54和24的最大公因数是多少？

数字54可以表示為几组不同正整數的乘積：

displaystyle 54=1times 54=2times 27=3times 18=6times 9

故54的正因數為 $displaystyle 1,2,3,6,9,18,27,54$ 。

同樣地，24可以表示為：

displaystyle 24=1times 24=2times 12=3times 8=4times 6

故24的正因數為 $displaystyle 1,2,3,4,6,8,12,24$ 。

这两组数列中的共同元素即为54和24的公因数：

displaystyle 1,2,3,6

其中的最大數6即為54和24的最大公因數，記為：

displaystyle gcd(54,24)=6

互质数

如果两数的最大公因数为1，那么这两个数互質。例如，9和28就是互质数。

几何角度的说明

24乘60的矩形被十个12乘12的正方形格子完全覆盖，即12为24和60的最大公因数。推而广之，如果c是a和b的最大公因数，那么a乘b的矩形就可以被若干个边长为c的正方形格子完全覆盖。

假设有一个大小为24乘60的矩形区域，这个区域可以按照不同的大小划分正方形网格：1乘1、2乘2、3乘3、4乘4、6乘6、12乘12。因此，12是24和60的最大公因数。大小为24乘60的矩形区域，可以按照12乘12的大小划分正方形网格，一边有两格（ $displaystyle frac 2412=2$ ）、另一边有五格（ $displaystyle frac 6012=5$ ）。

计算

质因数分解法

可以通过質因數分解来计算最大公因数。例如计算 $displaystyle gcd(18,84)$ ，可以先进行质因数分解 $displaystyle 18=2times 3^2$ 和 $displaystyle 84=2^2times 3times 7$ ，因为其中表达式 $displaystyle 2times 3$ 的「重合」，所以 $displaystyle gcd(18,84)=6$ 。实践中，这种方法只在数字比较小时才可行，因为对较大数进行质因数分解通常会耗费大量的时间。

再举一个用文氏图表示的例子，计算48和180的最大公因数。首先对这两个数进行质因数分解：

displaystyle 48=2times 2times 2times 2times 3

displaystyle 180=2times 2times 3times 3times 5

它们之中的共同元素是两个2和一个3：

^[1]

最小公倍数

displaystyle =2times 2times (2times 2times 3)times 3times 5=720

最大公因数

displaystyle =2times 2times 3=12

辗转相除法

相比质因数分解法，辗转相除法的效率更高。

计算 $displaystyle gcd(18,48)$ 时，先将48除以18得到商2、余数12，然后再将18除以12得到商1、余数6，再将12除以6得到商2、余数0，即得到最大公因数6。我们只关心每次除法的余数是否为0，为0即表示得到答案。这一算法更正式的描述是这样的：

displaystyle gcd(a,0)=a

displaystyle gcd(a,b)=gcd(b,a,mathrm mod ,b)

其中

displaystyle a,mathrm mod ,b=a-bleftlfloor a over brightrfloor

如果参数都大于0，那么该算法可以写成更简单的形式：

displaystyle gcd(a,a)=a

,

displaystyle gcd(a,b)=gcd(a-b,b)quad

如果 a > b

displaystyle gcd(a,b)=gcd(a,b-a)quad

如果 b > a

播放媒体

使用辗转相除法计算62和36的最大公因数2的演示动画。

性质

任意a和b的公因数都是 $displaystyle gcd(a,b)$ 的因數。

$displaystyle gcd$ 函数满足交换律： $displaystyle gcd(a,b)=gcd(b,a)$ 。

$displaystyle gcd$ 函数满足结合律： $displaystyle gcd(a,gcd(b,c))=gcd(gcd(a,b),c)$

程式代碼

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

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

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)

政治用法

最大公約數又指一社會中不同陣營勉強所達之共同利益。

参考文献

^ Gustavo Delfino, "Understanding the Least Common Multiple and Greatest Common Divisor", Wolfram Demonstrations Project, Published: February 1, 2013.

外部链接

圖解最大公因數求法

包含GCD動態規劃

参见

公倍数

公约数

最小公倍数

[1] Gustavo Delfino, "Understanding the Least Common Multiple and Greatest Common Divisor", Wolfram Demonstrations Project, Published: February 1, 2013.

搜尋此網誌