最大公因數 (英語:highest common factor ,hcf )也稱最大公約數 (英語:greatest common divisor ,gcd )是數學 詞彙,指能够整除 多個非零整數 的最大正整数。例如8和12的最大公因数为4。
整数序列
a
{\displaystyle a}
的最大公因数可以記為
(
a
1
,
a
2
,
…
,
a
n
)
{\displaystyle (a_{1},a_{2},\dots ,a_{n})}
或
gcd
(
a
1
,
a
2
,
…
,
a
n
)
{\displaystyle \gcd(a_{1},a_{2},\dots ,a_{n})}
。
最大公因数的值至少為1,例如
gcd
(
3
,
7
)
=
1
{\displaystyle \gcd(3,7)=1}
;最大則為該組整數中絕對值 最小的絕對值,例如
gcd
(
3
,
9
)
=
3
{\displaystyle \gcd(3,9)=3}
和
gcd
(
−
3
,
9
)
=
3
{\displaystyle \gcd(-3,9)=3}
。
求兩個整數最大公因數主要的方法:
列舉法:分別列出兩整數的所有因數 ,並找出最大的公因數。
質因數分解 :分別列出兩數的質因數分解式,並計算共同項的乘積 。
短除法 :兩數除以其共同質因數 ,直到兩數互質 時,所有除數的乘積即為最大公因數。兩個整數
a
,
b
{\displaystyle a,b}
的最大公因數和最小公倍數 (lcm )的關係為:
gcd
(
a
,
b
)
lcm
(
a
,
b
)
=
|
a
b
|
{\displaystyle \gcd(a,b)\operatorname {lcm} (a,b)=|ab|}
兩個整數的最大公因數可用於計算兩數的最小公倍數,或分數化簡成最簡分數 。
兩個整數的最大公因數和最小公倍數中存在分配律 :
gcd
(
a
,
lcm
(
b
,
c
)
)
=
lcm
(
gcd
(
a
,
b
)
,
gcd
(
a
,
c
)
)
{\displaystyle \gcd(a,\operatorname {lcm} (b,c))=\operatorname {lcm} (\gcd(a,b),\gcd(a,c))}
lcm
(
a
,
gcd
(
b
,
c
)
)
=
gcd
(
lcm
(
a
,
b
)
,
lcm
(
a
,
c
)
)
{\displaystyle \operatorname {lcm} (a,\gcd(b,c))=\gcd(\operatorname {lcm} (a,b),\operatorname {lcm} (a,c))}
在直角坐標 中,兩頂點 為
(
0
,
0
)
,
(
a
,
b
)
{\displaystyle (0,0),(a,b)}
的線段會通過
gcd
(
a
,
b
)
+
1
{\displaystyle \gcd(a,b)+1}
個格子點。
54和24的最大公因数是多少?
数字54可以表示為几组不同正整數的乘積:
54
=
1
×
54
=
2
×
27
=
3
×
18
=
6
×
9
{\displaystyle 54=1\times 54=2\times 27=3\times 18=6\times 9}
故54的正因數為
1
,
2
,
3
,
6
,
9
,
18
,
27
,
54
{\displaystyle 1,2,3,6,9,18,27,54}
。
同樣地,24可以表示為:
24
=
1
×
24
=
2
×
12
=
3
×
8
=
4
×
6
{\displaystyle 24=1\times 24=2\times 12=3\times 8=4\times 6}
故24的正因數為
1
,
2
,
3
,
4
,
6
,
8
,
12
,
24
{\displaystyle 1,2,3,4,6,8,12,24}
。
这两组数列中的共同元素即为54和24的公因数 :
1
,
2
,
3
,
6
{\displaystyle 1,2,3,6}
其中的最大數6即為54和24的最大公因數 ,記為:
gcd
(
54
,
24
)
=
6
{\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的大小划分正方形网格,一边有两格(
24
12
=
2
{\displaystyle {\frac {24}{12))=2}
)、另一边有五格(
60
12
=
5
{\displaystyle {\frac {60}{12))=5}
)。
可以通过質因數分解 来计算最大公因数。例如计算
gcd
(
18
,
84
)
{\displaystyle \gcd(18,84)}
,可以先进行质因数分解
18
=
2
×
3
2
{\displaystyle 18=2\times 3^{2))
和
84
=
2
2
×
3
×
7
{\displaystyle 84=2^{2}\times 3\times 7}
,因为其中表达式
2
×
3
{\displaystyle 2\times 3}
的「重合」,所以
gcd
(
18
,
84
)
=
6
{\displaystyle \gcd(18,84)=6}
。实践中,这种方法只在数字比较小时才可行,因为对较大数进行质因数分解通常会耗费大量的时间。
再举一个用文氏图 表示的例子,计算48和180的最大公因数。首先对这两个数进行质因数分解:
48
=
2
×
2
×
2
×
2
×
3
{\displaystyle 48=2\times 2\times 2\times 2\times 3}
180
=
2
×
2
×
3
×
3
×
5
{\displaystyle 180=2\times 2\times 3\times 3\times 5}
它们之中的共同元素是两个2和一个3:
[1] 最小公倍数
=
2
×
2
×
(
2
×
2
×
3
)
×
3
×
5
=
720
{\displaystyle =2\times 2\times (2\times 2\times 3)\times 3\times 5=720}
最大公因数
=
2
×
2
×
3
=
12
{\displaystyle =2\times 2\times 3=12}
相比质因数分解法,辗转相除法 的效率更高。
计算
gcd
(
18
,
48
)
{\displaystyle \gcd(18,48)}
时,先将48除以18得到商 2、余数 12,然后再将18除以12得到商1、余数6,再将12除以6得到商2、余数0,即得到最大公因数6。我们只关心每次除法的余数是否为0,为0即表示得到答案。这一算法更正式的描述是这样的:
gcd
(
a
,
0
)
=
a
{\displaystyle \gcd(a,0)=a}
gcd
(
a
,
b
)
=
gcd
(
b
,
a
m
o
d
b
)
{\displaystyle \gcd(a,b)=\gcd(b,a\,\mathrm {mod} \,b)}
其中
a
m
o
d
b
=
a
−
b
⌊
a
b
⌋
{\displaystyle a\,\mathrm {mod} \,b=a-b\left\lfloor {a \over b}\right\rfloor }
如果参数都大于0,那么该算法可以写成更简单的形式:
gcd
(
a
,
a
)
=
a
{\displaystyle \gcd(a,a)=a}
,
gcd
(
a
,
b
)
=
gcd
(
a
−
b
,
b
)
{\displaystyle \gcd(a,b)=\gcd(a-b,b)\quad }
如果 a > b
gcd
(
a
,
b
)
=
gcd
(
a
,
b
−
a
)
{\displaystyle \gcd(a,b)=\gcd(a,b-a)\quad }
如果 b > a 使用辗转相除法计算62和36的最大公因数2的演示动画。 任意a 和b 的公因数都是
gcd
(
a
,
b
)
{\displaystyle \gcd(a,b)}
的因數 。
gcd
{\displaystyle \gcd }
函数满足交换律 :
gcd
(
a
,
b
)
=
gcd
(
b
,
a
)
{\displaystyle \gcd(a,b)=\gcd(b,a)}
。
gcd
{\displaystyle \gcd }
函数满足结合律 :
gcd
(
a
,
gcd
(
b
,
c
)
)
=
gcd
(
gcd
(
a
,
b
)
,
c
)
{\displaystyle \gcd(a,\gcd(b,c))=\gcd(\gcd(a,b),c)}
以下使用輾轉相除法 實現。
private int GCD ( int a , int b ) {
if ( 0 != b ) while ( 0 != ( a %= b ) && 0 != ( b %= a ));
return a + b ;
}
运行时计算实现:
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
}
int GCD ( int a , int b ) {
if ( b ) while (( a %= b ) && ( b %= a ));
return a + b ;
}
private int GCD ( int a , int b ) {
if ( b == 0 ) return a ;
return GCD ( b , a % b );
}
const GCD = ( a , b ) => b ? GCD ( b , a % b ) : a ;
GCD = lambda a , b : ( a if b == 0 else GCD ( b , a % b ))
# or
def GCD ( a , b ):
if b == 0 :
return a
return GCD ( b , a % b )
最大公約數又指一社會中不同陣營勉強所達之共同利益。