最大公因數- 维基百科，自由的百科全书
文章推薦指數： 80 %
最大公因數（英語：highest common factor，簡稱hcf）也稱最大公約數（英語：greatest common divisor，簡稱gcd）是數學詞彙，指能够整除多個整數的最大正整数。
最大公因數
語言
監視
編輯
最大公因數（英語：highestcommonfactor，簡稱hcf）也稱最大公約數（英語：greatestcommondivisor，簡稱gcd）是數學詞彙，指能夠整除多個整數的最大正整數。
而多個整數不能都為零[1][2]。
例如8和12的最大公因數為4。
整數序列
a
{\displaystylea}
的最大公因數可以記為
(
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})}
。
求兩個整數最大公因數主要的方法：
列舉法：分別列出兩整數的所有因數，並找出最大的公因數。
質因數分解：分別列出兩數的質因數分解式，並計算共同項的乘積。
短除法：兩數除以其共同質因數，直到兩數互質時，所有除數的乘積即為最大公因數。
[3]
兩個整數
a
,
b
{\displaystylea,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}
個格子點。
目次
1概述
1.1例子
1.2互質數
1.3幾何角度的說明
2計算
2.1質因數分解法
2.2輾轉相除法
3性質
4程式代碼
4.1C#
4.2C++
4.3C
4.4Java
4.5JavaScript
4.6Python
5政治用法
6參考文獻
7外部連結
8參見
概述編輯
例子編輯
54和24的最大公因數是多少？
數字54可以表示為幾組不同正整數的乘積：
54
=
1
×
54
=
2
×
27
=
3
×
18
=
6
×
9
{\displaystyle54=1\times54=2\times27=3\times18=6\times9}
故54的正因數為
1
,
2
,
3
,
6
,
9
,
18
,
27
,
54
{\displaystyle1,2,3,6,9,18,27,54}
。
同樣地，24可以表示為：
24
=
1
×
24
=
2
×
12
=
3
×
8
=
4
×
6
{\displaystyle24=1\times24=2\times12=3\times8=4\times6}
故24的正因數為
1
,
2
,
3
,
4
,
6
,
8
,
12
,
24
{\displaystyle1,2,3,4,6,8,12,24}
。
這兩組數列中的共同元素即為54和24的公因數：
1
,
2
,
3
,
6
{\displaystyle1,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
{\displaystyle18=2\times3^{2}}
和
84
=
2
2
×
3
×
7
{\displaystyle84=2^{2}\times3\times7}
，因為其中表達式
2
×
3
{\displaystyle2\times3}
的「重合」，所以
gcd
(
18
,
84
)
=
6
{\displaystyle\gcd(18,84)=6}
。
實踐中，這種方法只在數字比較小時才可行，因為對較大數進行質因數分解通常會耗費大量的時間。
再舉一個用文氏圖表示的例子，計算48和180的最大公因數。
首先對這兩個數進行質因數分解：
48
=
2
×
2
×
2
×
2
×
3
{\displaystyle48=2\times2\times2\times2\times3}
180
=
2
×
2
×
3
×
3
×
5
{\displaystyle180=2\times2\times3\times3\times5}
它們之中的共同元素是兩個2和一個3：
[4]最小公倍數
=
2
×
2
×
(
2
×
2
×
3
)
×
3
×
5
=
720
{\displaystyle=2\times2\times(2\times2\times3)\times3\times5=720}
最大公因數
=
2
×
2
×
3
=
12
{\displaystyle=2\times2\times3=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
⌋
{\displaystylea\,\mathrm{mod}\,b=a-b\left\lfloor{a\overb}\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)}
程式代碼編輯
數字之間的最大公因數之所有因數是該組數字所有的公因數。
以下使用輾轉相除法實現。
C#編輯
privateintGCD(inta,intb){
if(0!=b)while(0!=(a%=b)&&0!=(b%=a));
returna+b;
}
C++編輯
運行時計算實現：
template
(2020年8月30日)參見：共識決策法和香港核心價值
最大公約數又指一社會中不同陣營勉強所達之共同利益。
參考文獻編輯
^GreatestCommonFactor.www.mathsisfun.com.[2022-07-30].
^https://byjus.com/maths/highest-common-factor/.BYJUS.[2022-07-30]（英語）. 外部連結存在於|title=(幫助)
^Primefactors-Multiplesandfactors-Edexcel-GCSEMathsRevision-Edexcel.BBCBitesize.[2022-07-30]（英國英語）.
^GustavoDelfino,"UnderstandingtheLeastCommonMultipleandGreatestCommonDivisor",[[WolframDemonstrationsProject]],Published:February1,2013..[2018-06-11].（原始內容存檔於2020-09-22）.
外部連結編輯
圖解最大公因數求法（頁面存檔備份，存於網際網路檔案館）
包含GCD動態規劃（頁面存檔備份，存於網際網路檔案館）參見編輯
公倍數
公因數
最小公倍數
取自「https://zh.wikipedia.org/w/index.php?title=最大公因數&oldid=72977128」
延伸文章資訊
- 1最大公约数和最小公倍数的英文缩写是什么？ - 百度知道
最大公约数和最小公倍数的英文缩写是什么？ 3个回答 ... greatest common factor 最大公因子 ... 最大公因数和最小公倍数的特征是什么?
- 2最大公因数英文简写 - 翻译知识网
最大公约数lowest common multiple 最小公倍数. 的英文缩写,俨然已经成为世界各地许多特警的代名词,包括美加各地与我国的霹雳小组.
- 3最大公因數
幾個數的公因數中最大的一個，稱為這幾個數的最大公因數。英文簡稱為HCF。 例：. 12和18的公因數有1、2、3、6，其中6就是12和18的最大公因數。 25和125的公因數 ...
- 4最大公因數英文縮寫在PTT/Dcard完整相關資訊
| Yahoo奇摩知識+tw.answers.yahoo.com 的其他相關資訊最大公因數兩個或多個數的公因數(公因子) (Factor) 中最大的一個稱為最大公因數。 HCF 又稱為gcd，分...
- 5最大公因數
兩個或多個數的公因數(公因子) (Factor) 中最大的一個稱為最大公因數。 HCF 又稱為gcd，分別為Highest Common Factor 及greatest common divi...
