最大公因數- 維基百科，自由的百科全書
文章推薦指數： 80 %
最大公因數（英語：highest common factor，hcf）也稱最大公約數（英語：greatest common divisor，gcd）是數學詞彙，指能夠整除多個整數的最大正整數。
而多個整數不能都為 ...
最大公因數
維基百科，自由的百科全書
跳至導覽
跳至搜尋
最大公因數（英語：highestcommonfactor，hcf）也稱最大公約數（英語：greatestcommondivisor，gcd）是數學詞彙，指能夠整除多個整數的最大正整數。
而多個整數不能都為零。
例如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})}
。
求兩個整數最大公因數主要的方法：
列舉法：分別列出兩整數的所有因數，並找出最大的公因數。
質因數分解：分別列出兩數的質因數分解式，並計算共同項的乘積。
短除法：兩數除以其共同質因數，直到兩數互質時，所有除數的乘積即為最大公因數。
兩個整數
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：
[1]
最小公倍數
=
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日)
參見：共識決策法和香港核心價值
最大公約數又指一社會中不同陣營勉強所達之共同利益。
參考文獻[編輯]
^GustavoDelfino,"UnderstandingtheLeastCommonMultipleandGreatestCommonDivisor",[[WolframDemonstrationsProject]],Published:February1,2013..[2018-06-11].（原始內容存檔於2020-09-22）.
外部連結[編輯]
圖解最大公因數求法（頁面存檔備份，存於網際網路檔案館）
包含GCD動態規劃（頁面存檔備份，存於網際網路檔案館）
參見[編輯]
公倍數
公因數
最小公倍數
取自「https://zh.wikipedia.org/w/index.php?title=最大公因數&oldid=69280698」
分類：積性函數數論算術二元運算隱藏分類：含有英語的條目自2020年8月擴充中的條目所有擴充中的條目拒絕當選首頁新條目推薦欄目的條目使用小型訊息框的頁面
導覽選單
個人工具
沒有登入討論貢獻建立帳號登入
命名空間
條目討論
臺灣正體
已展開
已摺疊
不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體
查看
閱讀編輯檢視歷史
更多
已展開
已摺疊
搜尋
導航
首頁分類索引特色內容新聞動態近期變更隨機條目資助維基百科
說明
說明維基社群方針與指引互助客棧知識問答字詞轉換IRC即時聊天聯絡我們關於維基百科
工具
連結至此的頁面相關變更上傳檔案特殊頁面靜態連結頁面資訊引用此頁面維基數據項目
列印/匯出
下載為PDF可列印版
其他專案
維基共享資源
其他語言
AlemannischالعربيةAsturianuAzərbaycancaБеларускаяБългарскиবাংলাBosanskiCatalàکوردیČeštinaЧӑвашлаCymraegDanskDeutschΕλληνικάEnglishEsperantoEspañolEestiEuskaraفارسیSuomiFrançaisGalegoעבריתहिन्दीHrvatskiMagyarՀայերենBahasaIndonesiaIdoÍslenskaItaliano日本語Қазақшаಕನ್ನಡ한국어LugandaLombardLietuviųLatviešuമലയാളംМонголBahasaMelayuPlattdüütschNederlandsNorskbokmålଓଡ଼ିଆਪੰਜਾਬੀPolskiPiemontèisPortuguêsRomânăРусскийSrpskohrvatski/српскохрватскиසිංහලSimpleEnglishSlovenčinaSlovenščinaShqipСрпски/srpskiSvenskaதமிழ்తెలుగుไทยTagalogTürkçeТатарча/tatarçaУкраїнськаاردوTiếngViệt吴语ייִדיש粵語
編輯連結
延伸文章資訊
- 1最大公因數與最小公倍數 - 均一教育平台
【例題】列出所有公因數，並求最大公因數. Exercise. 【基礎】公因數與最大公因數. Video. 【觀念】互質. Video. 【例題】判斷兩數是否互質.
- 212 和18 的公因數1、2、3
教學小叮嚀：親師宜引導學童透過短除法進行各數的質因數分解，找出兩數相同的質因數相. 乘，而找出兩數的最大公因數。 本教材著作財產權為教育部國民及學前教育署所有 ...
- 3最大公因數計算器 - Nap.st
這是一個可以輕鬆找到最大公因數的程序。 輸入值並點擊/單擊“運行”，程序將計算並顯示它們的G.C.D. G.C.D. 是"Greatest Common Divisor" 的縮寫。
- 4主題四公因數、公倍數與互質 - 教育部
事實上, 兩整數的公因數常常有很多個, 此時, 我們把這些公因數中. 最大的數命名為最大公因數｡ 本教材著作財產權為教育部國民及學前教育署所有. Page 4 ...
- 5最大公因數、最小公倍數線上計算機 - Live數學學習網
Live動態數學的兩台最大公因數與最小公倍數的線上計算機，方便你多工處理計算。將要求最大公因數或最小公倍數的兩數，分別填入A、B欄位，接著按下『計算』， ...
