最大公因數- 维基百科，自由的百科全书
文章推薦指數： 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
Playmedia使用辗转相除法计算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最大公因數
兩個或多個數的公因數(公因子) (Factor) 中最大的一個稱為最大公因數。 HCF 又稱為gcd，分別為Highest Common Factor 及greatest common divi...
- 2最大公因数？其英文说法是什么？（附举例） - 学习志
英文中，公因数的说法是：common factor。而最大公因数的英语则是：greatest common factor。 注：本文由学习志（Alearnersblog.com）原创，最后更新 ...
- 3greatest common divisor - 最大公約數 - 國家教育研究院雙語詞彙
出處/學術領域, 英文詞彙, 中文詞彙. 學術名詞 數學名詞-兩岸中小學教科書名詞, greatest common divisor, 最大公因子；最大公因數. 學術名詞
- 4最大公因數英文- 數學名詞- 雙語詞彙 - 三度漢語網
- 5最大公因數英文縮寫在PTT/Dcard完整相關資訊
| Yahoo奇摩知識+tw.answers.yahoo.com 的其他相關資訊最大公因數兩個或多個數的公因數(公因子) (Factor) 中最大的一個稱為最大公因數。 HCF 又稱為gcd，分...
