精選百科
本文由作者推薦
小編整理：
最大公約數(shù)指兩個(gè)或多個(gè)整數(shù)共有約數(shù)中最大的一個(gè)。 您可以使用輾轉(zhuǎn)相除法來(lái)計(jì)算兩個(gè)數(shù)的最大公約數(shù)，也可以使用輾轉(zhuǎn)相減法來(lái)計(jì)算最大公約數(shù)。 輾轉(zhuǎn)相除法計(jì)算最大公約數(shù)的步驟如下： 1. 用較大數(shù)除以較小數(shù)，再用出現(xiàn)的余數(shù)去除較小的數(shù)，如此反復(fù)。 2. 直到余數(shù)為零為止，此時(shí)較小數(shù)即為兩數(shù)的最大公約數(shù)。 例如，計(jì)算12和18的最大公約數(shù)，可以按照如下步驟進(jìn)行： 12 ÷ 18 = 0......12 18 ÷ 12 = 1......6 12 ÷ 6 = 2......0 因此，6就是12和18的最大公約數(shù)。 以上就是關(guān)于最大公約數(shù)的解讀，希望對(duì)您有所幫助。最大公約數(shù)
最大公因數(shù)
兩個(gè)或多個(gè)整數(shù)共有約數(shù)中最大的一個(gè)
最大公因數(shù)，也稱(chēng)最大公約數(shù)、最大公因子，指兩個(gè)或多個(gè)整數(shù)共有約數(shù)中最大的一個(gè)。a，b的最大公約數(shù)記為（a，b），同樣的，a，b，c的最大公約數(shù)記為（a，b，c），多個(gè)整數(shù)的最大公約數(shù)也有同樣的記號(hào)。求最大公約數(shù)有多種方法，常見(jiàn)的有質(zhì)因數(shù)分解法、短除法、輾轉(zhuǎn)相除法、更相減損法。與最大公約數(shù)相對(duì)應(yīng)的概念是最小公倍數(shù)，a，b的最小公倍數(shù)記為[a，b]。
基本信息
| 中文名 | 最大公約數(shù) |
| 外文名 | Greatest Common Divisor(GCD) |
| 別名 | Highest Common Factor(HCF) |
| 應(yīng)用學(xué)科 | 數(shù)學(xué) |
| 相對(duì)應(yīng)概念 | 最小公倍數(shù) |
| 基本概念 | 多個(gè)整數(shù)共有約數(shù)中最大的一個(gè) |
收起
基本概念
如果數(shù)a能被數(shù)b整除，a就叫做b的倍數(shù)，b就叫做a的約數(shù)。約數(shù)和倍數(shù)都表示一個(gè)整數(shù)與另一個(gè)整數(shù)的關(guān)系，不能單獨(dú)存在。如只能說(shuō)16是某數(shù)的倍數(shù)，2是某數(shù)的約數(shù)，而不能孤立地說(shuō)16是倍數(shù)，2是約數(shù)。
"倍"與"倍數(shù)"是不同的兩個(gè)概念，"倍"是指兩個(gè)數(shù)相除的商，它可以是整數(shù)、小數(shù)或者分?jǐn)?shù)。"倍數(shù)"只是在數(shù)的整除的范圍內(nèi)，相對(duì)于"約數(shù)"而言的一個(gè)數(shù)字的概念，表示的是能被某一個(gè)自然數(shù)整除的數(shù)。
幾個(gè)整數(shù)中公有的約數(shù)，叫做這幾個(gè)數(shù)的公約數(shù)；其中最大的一個(gè)，叫做這幾個(gè)數(shù)的最大公約數(shù)。例如：12、16的公約數(shù)有1、2、4，其中最大的一個(gè)是4，4是12與16的最大公約數(shù)，一般記為（12，16）=4。12、15、18的最大公約數(shù)是3，記為（12，15，18）=3。
幾個(gè)自然數(shù)公有的倍數(shù)，叫做這幾個(gè)數(shù)的公倍數(shù)，其中最小的一個(gè)自然數(shù)，叫做這幾個(gè)數(shù)的最小公倍數(shù)。例如：4的倍數(shù)有4、8、12、16，……，6的倍數(shù)有6、12、18、24，……，4和6的公倍數(shù)有12、24，……，其中最小的是12，一般記為[4，6]=12。12、15、18的最小公倍數(shù)是180。記為[12，15，18]=180。若干個(gè)互質(zhì)數(shù)的最小公倍數(shù)為它們的乘積的絕對(duì)值。
最大公約數(shù)
求法
質(zhì)因數(shù)分解法
質(zhì)因數(shù)分解法：把每個(gè)數(shù)分別分解質(zhì)因數(shù)，再把各數(shù)中的全部公有質(zhì)因數(shù)提取出來(lái)連乘，所得的積就是這幾個(gè)數(shù)的最大公約數(shù)。
例如：求24和60的最大公約數(shù)，先分解質(zhì)因數(shù)，得24=2×2×2×3，60=2×2×3×5，24與60的全部公有的質(zhì)因數(shù)是2、2、3，它們的積是2×2×3=12，所以，（24，60）=12。
把幾個(gè)數(shù)先分別分解質(zhì)因數(shù)，再把各數(shù)中的全部公有的質(zhì)因數(shù)和獨(dú)有的質(zhì)因數(shù)提取出來(lái)連乘，所得的積就是這幾個(gè)數(shù)的最小公倍數(shù)。
例如：求6和15的最小公倍數(shù)。先分解質(zhì)因數(shù)，得6=2×3，15=3×5，6和15的全部公有的質(zhì)因數(shù)是3，6獨(dú)有質(zhì)因數(shù)是2，15獨(dú)有的質(zhì)因數(shù)是5，2×3×5=30，30里面包含6的全部質(zhì)因數(shù)2和3，還包含了15的全部質(zhì)因數(shù)3和5，且30是6和15的公倍數(shù)中最小的一個(gè)，所以[6，15]=30。
短除法
短除法：短除法求最大公約數(shù)，先用這幾個(gè)數(shù)的公約數(shù)連續(xù)去除，一直除到所有的商互質(zhì)為止，然后把所有的除數(shù)連乘起來(lái)，所得的積就是這幾個(gè)數(shù)的最大公約數(shù)。
短除法求最小公倍數(shù)，先用這幾個(gè)數(shù)的公約數(shù)去除每個(gè)數(shù)，再用部分?jǐn)?shù)的公約數(shù)去除，并把不能整除的數(shù)移下來(lái)，一直除到所有的商中每?jī)蓚€(gè)數(shù)都是互質(zhì)的為止，然后把所有的除數(shù)和商連乘起來(lái)，所得的積就是這幾個(gè)數(shù)的最小公倍數(shù)，例如，求12、15、18的最小公倍數(shù)。
短除法的本質(zhì)就是質(zhì)因數(shù)分解法，只是將質(zhì)因數(shù)分解用短除符號(hào)來(lái)進(jìn)行。
短除符號(hào)就是除號(hào)倒過(guò)來(lái)。短除就是在除法中寫(xiě)除數(shù)的地方寫(xiě)兩個(gè)數(shù)共有的質(zhì)因數(shù)，然后落下兩個(gè)數(shù)被公有質(zhì)因數(shù)整除的商，之后再除，以此類(lèi)推，直到結(jié)果互質(zhì)為止（兩個(gè)數(shù)互質(zhì)）。
而在用短除計(jì)算多個(gè)數(shù)時(shí)，對(duì)其中任意兩個(gè)數(shù)存在的因數(shù)都要算出，其它沒(méi)有這個(gè)因數(shù)的數(shù)則原樣落下。直到剩下每?jī)蓚€(gè)都是互質(zhì)關(guān)系。
求最大公因數(shù)便乘一邊，求最小公倍數(shù)便乘一圈。
無(wú)論是短除法，還是分解質(zhì)因數(shù)法，在質(zhì)因數(shù)較大時(shí)，都會(huì)覺(jué)得困難。這時(shí)就需要用新的方法。
輾轉(zhuǎn)相除法
輾轉(zhuǎn)相除法：輾轉(zhuǎn)相除法是求兩個(gè)自然數(shù)的最大公約數(shù)的一種方法，也叫歐幾里德算法。
例如，求（319，377）：
∵ 319÷377=0（余319）
∴（319，377）=（377，319）；
∵ 377÷319=1（余58）
∴（377，319）=（319，58）；
∵ 319÷58=5（余29）
∴ （319，58）=（58，29）；
∵ 58÷29=2（余0）
∴ （58，29）= 29；
∴ （319，377）=29。
可以寫(xiě)成右邊的格式。
用輾轉(zhuǎn)相除法求幾個(gè)數(shù)的最大公約數(shù)，可以先求出其中任意兩個(gè)數(shù)的最大公約數(shù)，再求這個(gè)最大公約數(shù)與第三個(gè)數(shù)的最大公約數(shù)，依次求下去，直到最后一個(gè)數(shù)為止。最后所得的那個(gè)最大公約數(shù)，就是所有這些數(shù)的最大公約數(shù)。
更相減損法
更相減損法：也叫更相減損術(shù)，是出自《九章算術(shù)》的一種求最大公約數(shù)的算法，它原本是為約分而設(shè)計(jì)的，但它適用于任何需要求最大公約數(shù)的場(chǎng)合。
《九章算術(shù)》是中國(guó)古代的數(shù)學(xué)專(zhuān)著，其中的“更相減損術(shù)”可以用來(lái)求兩個(gè)數(shù)的最大公約數(shù)，即“可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也。以等數(shù)約之。”
翻譯成現(xiàn)代語(yǔ)言如下：
第一步：任意給定兩個(gè)正整數(shù)；判斷它們是否都是偶數(shù)。若是，則用2約簡(jiǎn)；若不是則執(zhí)行第二步。
第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止。
則第一步中約掉的若干個(gè)2與第二步中等數(shù)的乘積就是所求的最大公約數(shù)。
其中所說(shuō)的“等數(shù)”，就是最大公約數(shù)。求“等數(shù)”的辦法是“更相減損”法。所以更相減損法也叫等值算法。
例1．用更相減損術(shù)求98與63的最大公約數(shù)。
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
所以，98和63的最大公約數(shù)等于7。
這個(gè)過(guò)程可以簡(jiǎn)單的寫(xiě)為：
（98，63）=（35，63）=（35，28）=（7，28）=（7，21）=（7，14）=（7，7）=7.
例2．用更相減損術(shù)求260和104的最大公約數(shù)。
解：由于260和104均為偶數(shù)，首先用2約簡(jiǎn)得到130和52，再用2約簡(jiǎn)得到65和26。
此時(shí)65是奇數(shù)而26不是奇數(shù)，故把65和26輾轉(zhuǎn)相減：
65-26=39
39-26=13
26-13=13
所以，260與104的最大公約數(shù)等于13乘以第一步中約掉的兩個(gè)2，即13*2*2=52。
這個(gè)過(guò)程可以簡(jiǎn)單地寫(xiě)為：
（260,104）(/2/2) =>（65,26）=（39,26）=（13,26）=（13,13）=13. (*2*2) => 52
比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別
（1）都是求最大公因數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)的區(qū)別較明顯。
（2）從結(jié)果體現(xiàn)形式來(lái)看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到。
常用結(jié)論
在解有關(guān)最大公約數(shù)、最小公倍數(shù)的問(wèn)題時(shí)，常用到以下結(jié)論：
（1）如果兩個(gè)自然數(shù)是互質(zhì)數(shù)，那么它們的最大公約數(shù)是1，最小公倍數(shù)是這兩個(gè)數(shù)的乘積。
例如8和9，它們是互質(zhì)數(shù)，所以（8，9）=1，[8，9]=72。
（2）如果兩個(gè)自然數(shù)中，較大數(shù)是較小數(shù)的倍數(shù)，那么較小數(shù)就是這兩個(gè)數(shù)的最大公約數(shù)，較大數(shù)就是這兩個(gè)數(shù)的最小公倍數(shù)。
例如18與3，18÷3=6，所以（18，3）=3，[18，3]=18。
（3）兩個(gè)整數(shù)分別除以它們的最大公約數(shù)，所得的商是互質(zhì)數(shù)。
例如8和14分別除以它們的最大公約數(shù)2，所得的商分別為4和7，那么4和7是互質(zhì)數(shù)。
（4）兩個(gè)自然數(shù)的最大公約數(shù)與它們的最小公倍數(shù)的乘積等于這兩個(gè)數(shù)的乘積。
例如12和16，（12，16）=4，[12，16]=48，有4×48=12×16，即（12，16）× [12，16]=12×16。
（5）GCD(a,b) is the smallest positive linear combination of a and b. a與b的最大公約數(shù)是最小的a與b的正線性組合，即對(duì)于方程xa+yb=c來(lái)說(shuō)，若x,a,y,b都為整數(shù)，那么c的最小正根為gcd(a,b).
歷史發(fā)展
在求解最大公約數(shù)的幾種方法中，輾轉(zhuǎn)相除法最為出名。輾轉(zhuǎn)相除法是仍然在使用的歷史最悠久的算法之一。它首次出現(xiàn)于幾何原本（卷7命題1–2、卷10命題2–3）（大約公元前300年）。在卷7中用于整數(shù)，在卷10中用于線段的長(zhǎng)度（也就是所說(shuō)的實(shí)數(shù)，但是當(dāng)時(shí)未有實(shí)數(shù)的概念）。卷10中出現(xiàn)的算法是幾何的，兩段線段a和b的最大公約數(shù)是準(zhǔn)確測(cè)量a和b的最大長(zhǎng)度。
這個(gè)算法可能并非歐幾里得發(fā)明，而僅僅是將先人的結(jié)果編進(jìn)他的幾何原本。數(shù)學(xué)家、歷史學(xué)家范德瓦爾登認(rèn)為卷7的內(nèi)容可能來(lái)自畢達(dá)哥拉斯學(xué)院出身的數(shù)學(xué)家寫(xiě)的關(guān)于數(shù)論的教科書(shū)。輾轉(zhuǎn)相除法是被大約公元前375年的歐多克斯發(fā)現(xiàn)的，但也有可能更早之前就已經(jīng)存在，因?yàn)闅W幾里得和亞里士多德的這兩位歷史名人著作中都出現(xiàn)了?νθυφα?ρεσι?一詞（anthyphairesis, 意為“輾轉(zhuǎn)相減”），
幾個(gè)世紀(jì)之后，輾轉(zhuǎn)相除法又分別被中國(guó)人和印度人獨(dú)立發(fā)現(xiàn)，主要用來(lái)解天文學(xué)中用到的丟番圖方程以及指定準(zhǔn)確的歷法。5世紀(jì)末，印度數(shù)學(xué)家、天文學(xué)家阿里亞哈塔可能是因?yàn)檩氜D(zhuǎn)相除法在解丟番圖方程時(shí)的高效率而稱(chēng)它為“粉碎機(jī)”。因?yàn)樵谥袊?guó)，孫子算經(jīng)中出現(xiàn)了此算法的一個(gè)特例中國(guó)剩余定理，但是輾轉(zhuǎn)相除法的完整表述直到1247年秦九韶的數(shù)學(xué)九章中才出現(xiàn)。在歐洲，輾轉(zhuǎn)相除法首次出現(xiàn)于克勞德·巴希特（英語(yǔ)：Claude Gaspard Bachet de Méziriac）的著作Problèmes plaisants et délectables的第二版在歐洲，輾轉(zhuǎn)相除法廣泛使用于丟番圖方程和連分?jǐn)?shù)。后來(lái)，英國(guó)數(shù)學(xué)家桑德森（英語(yǔ)：Nicholas Saunderson）將擴(kuò)展歐幾里得算法作為羅杰科茨（英語(yǔ)：Roger Cotes）對(duì)計(jì)算連分?jǐn)?shù)的方法的研究發(fā)表。
19世紀(jì)，輾轉(zhuǎn)相除法孕育出了一些新的數(shù)系，如高斯整數(shù)和艾森斯坦整數(shù)。1815年，高斯用輾轉(zhuǎn)相除法證明高斯整數(shù)的分解是惟一的，他的研究發(fā)表于1832年。高斯在他的《算數(shù)研究》（published 1801）中，作為處理連分?jǐn)?shù)的方法提到了這個(gè)算法。約翰·狄利克雷是第一個(gè)將輾轉(zhuǎn)相除法作為數(shù)論的基礎(chǔ)的數(shù)學(xué)家。狄利克雷提出，數(shù)論中的很多結(jié)論，如分解的惟一性，在任何使輾轉(zhuǎn)相除法成立的數(shù)系中有效。狄利克雷的觀點(diǎn)被理查德·戴德金修改和推廣，他用輾轉(zhuǎn)相除法研究代數(shù)整數(shù)。戴德金是第一個(gè)用高斯整數(shù)的分解惟一性證明費(fèi)馬平方和定理的數(shù)學(xué)家。戴德金還率先定義了歐幾里得整環(huán)的概念。19世紀(jì)末，輾轉(zhuǎn)相除法的輝煌逐漸被戴德金的理想取代。
輾轉(zhuǎn)相除法的其他應(yīng)用發(fā)展于19世紀(jì)。1829年，施圖姆將輾轉(zhuǎn)相除法用于施圖姆序列（用于確定多項(xiàng)式的不同實(shí)根的個(gè)數(shù)的方法）。
輾轉(zhuǎn)相除法是歷史上第一個(gè)整數(shù)關(guān)系算法（英語(yǔ)：integer relation algorithm），即尋找兩數(shù)的整數(shù)關(guān)系的算法。近年來(lái)，出現(xiàn)了一些新穎的整數(shù)關(guān)系算法，如埃拉曼·弗格森（英語(yǔ)：Helaman Ferguson）和福爾卡德于1979年發(fā)表的弗格森-福爾卡德算法、以及與它相關(guān)的LLL算法（英語(yǔ)：Lenstra–Lenstra–Lovász lattice basis reduction algorithm）、HJLS算法以及PSLQ算法（英語(yǔ)：PSLQ algorithm）。
1969年，科爾(Cole)和戴維(Davie)基于輾轉(zhuǎn)相除法創(chuàng)造了一種二人游戲，叫做歐幾里得游戲。這個(gè)游戲有最優(yōu)策略。游戲開(kāi)始于兩列分別為a和b個(gè)棋子組成的序列，玩家輪流從較長(zhǎng)一列中取走較短一列棋子數(shù)量的m倍的棋子。如果兩列棋子a和b分別由x和y個(gè)棋子組成，其中x大于y，那么玩家可以序列a的棋子數(shù)量減少為自然數(shù)x ? my。最后率先將一列棋子清空的玩家勝出。
擴(kuò)展歐幾里得算法
擴(kuò)展歐幾里德算法：擴(kuò)展歐幾里得算法（又稱(chēng)擴(kuò)充歐幾里得算法）是用來(lái)解某一類(lèi)特定的不定方程的一種方法，常用用來(lái)求解模線性方程及方程組。擴(kuò)展的歐幾里得算法可以用來(lái)計(jì)算模逆元，而模逆元在公鑰密碼學(xué)中占有舉足輕重的地位。
基本算法：對(duì)于不完全為 0 的非負(fù)整數(shù) a，b，gcd（a，b）表示 a，b 的最大公約數(shù)，必然存在整數(shù)對(duì) x，y ，使得 gcd（a，b）=ax+by。
證明：設(shè) a>b。
1，顯然當(dāng) b=0，gcd（a，b）=a。此時(shí) x=1，y=0；
2，ab≠0 時(shí)
設(shè) ax1+by1=gcd(a,b);
bx2+(a mod b)y2=gcd(b,a mod b);
根據(jù)樸素的歐幾里德原理有 gcd(a,b)=gcd(b,a mod b);
則：ax1+by1=bx2+(a mod b)y2;
即：ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
根據(jù)恒等定理得：x1=y2; y1=x2-(a/b)*y2;
這樣我們就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.
上面的思想是以遞歸定義的，因?yàn)?gcd 不斷的遞歸求解一定會(huì)有個(gè)時(shí)候 b=0，所以遞歸可以結(jié)束。
歐幾里德算法是計(jì)算兩個(gè)數(shù)最大公約數(shù)的傳統(tǒng)算法，無(wú)論從理論還是從實(shí)際效率上都是很好的。但是卻有一個(gè)致命的缺陷，這個(gè)缺陷在素?cái)?shù)比較小的時(shí)候一般是感覺(jué)不到的，只有在大素?cái)?shù)時(shí)才會(huì)顯現(xiàn)出來(lái)。
Stein算法由J. Stein 1961年提出，這個(gè)方法也是計(jì)算兩個(gè)數(shù)的最大公約數(shù)。和歐幾里德算法算法不同的是，Stein算法只有整數(shù)的移位和加減法，這對(duì)于程序設(shè)計(jì)者是一個(gè)福音。
Stein算法：
設(shè)置A1=A、B1=B和C1=1
1、如果An=0，Bn*Cn是最大公約數(shù)，算法結(jié)束
2、如果Bn=0，An*Cn是最大公約數(shù)，算法結(jié)束
3、如果An和Bn都是偶數(shù)，則An+1=An/2，Bn+1=Bn/2，Cn+1=Cn*2(注意，乘2只要把整數(shù)左移一位即可，除2只要把整數(shù)右移一位即可)
4、如果An是偶數(shù)，Bn不是偶數(shù)，則An+1=An/2，Bn+1=Bn，Cn+1=Cn (很顯然啦，2不是奇數(shù)的約數(shù))
5、如果Bn是偶數(shù)，An不是偶數(shù)，則Bn+1=Bn/2，An+1=An，Cn+1=Cn (很顯然啦，2不是奇數(shù)的約數(shù))
6、如果An和Bn都不是偶數(shù)，則An+1=|An-Bn|，Bn+1=min(An,Bn)，Cn+1=Cn
7、n加1，轉(zhuǎn)步驟1
考慮歐幾里德算法，最?lèi)毫拥那闆r是，每次迭代a=2b-1,這樣，迭代后，r=b-1。如果a小于2N，這樣大約需要4N次迭代。而考慮Stein算法，每次迭代后，顯然A(n+1)B(n+1)≤AnBn/2，最大迭代次數(shù)也不超過(guò)4N次。也就是說(shuō)，迭代次數(shù)幾乎是相等的。但是，需要注意的是，對(duì)于大素?cái)?shù)，試商法將使每次迭代都更復(fù)雜，因此對(duì)于大素?cái)?shù)Stein將更有優(yōu)勢(shì)。
性質(zhì)
gcd(-a,b)=gcd(a,b)
gcd(a,a)=|a|
gcd(a,0)=|a|
gcd(a,1)=1
gcd(a,b)=gcd(b, a mod b)
gcd(a,b)=gcd(b, a-b)
如果有附加的一個(gè)自然數(shù)m,
gcd(a+mb ,b)=gcd(a,b)
如果m是a和b的最大公約數(shù)，
則： gcd(a/m ,b/m)=gcd(a,b)/m
在乘法函數(shù)中有：
gcd(ab,m)=gcd(a,m) * gcd(b,m)
兩個(gè)整數(shù)的最大公約數(shù)主要有兩種尋找方法：
* 兩數(shù)各分解質(zhì)因數(shù)，然后取出同樣有的質(zhì)因數(shù)乘起來(lái)
*輾轉(zhuǎn)相除法（擴(kuò)展版）
和最小公倍數(shù)（lcm）的關(guān)系：
gcd(a, b) * lcm(a, b) = ab
a與b有最大公約數(shù)，
兩個(gè)整數(shù)的最大公因子和最小公倍數(shù)中存在分配律：
* gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))
* lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))
在坐標(biāo)里，將點(diǎn)(0, 0)和(a, b)連起來(lái)，通過(guò)整數(shù)坐標(biāo)的點(diǎn)的數(shù)目（除了(0, 0)一點(diǎn)之外）就是gcd(a, b)。
程序?qū)崿F(xiàn)
Java實(shí)現(xiàn)
importjava.util.Scanner;
publicclassSix{
publicstaticvoidmain(String[]args){
System.out.print("請(qǐng)輸入a和b");
Scannerscan=newScanner(System.in);//以空格作為分隔符
inta=scan.nextInt();
intb=scan.nextInt();
intmiddle1,middle2,middle3;
middle1=a;
middle2=b;
middle3=0;
for(inti=0;i
middle3=middle1%middle2;
if(middle3==0)
break;
else{
middle1=middle2;
middle2=middle3;
}
}
System.out.println("最大公約數(shù)為："+middle2);
}
}
PASCAL
programzuidagongyueshu;varm,n,a,b,r:integer;begin//主程序write('Inputm,n=');readln(m,n);a:=m;b:=n;repeatr:=amodb;a:=b;b:=r;untilrb=0;writeln('Thegreatestcommondivideis:',a);end.
programgcd;vark,a,b:integer;functiongcd(a,b:integer):integer;beginifamodb=0thenexit(b)elsegcd:=gcd(b,amodb);end;beginreadln(a,b);k:=gcd(a,b);writeln(k);end.
#includeintmain(){intm,n,i;scanf("%d",&m);scanf("%d",&n);for(i=m;i>=1;i--)if(m%i==0&&n%i==0)break;printf("%d
",i);return0;}
遞歸算法
1.C語(yǔ)言程序如下：#include#include/**最大公約數(shù)的遞歸：*1、若a可以整除b，則最大公約數(shù)是b*2、如果1不成立，最大公約數(shù)便是b與a%b的最大公約數(shù)*示例：求(140,21)*140%21=14*21%14=7*14%7=0*返回7**/intgcd(inta,intb){if(a%b==0)returnb;returngcd(b,a%b);}intmain(void){inta=10,b=8;scanf("%d%d",&a,&b);printf("GCD:A=>%d,B=>%d(A,B)=%d
",a,b,gcd(a,b));return0;}
C++:intgcd(inta,intb){inttemp;while(b){/*利用輾除法，直到b為0為止*/temp=b;b=a%b;a=temp;}returna;}分?jǐn)?shù)的最大公約數(shù)為：例（5/6，5/9）=（5,5）/【6,9】=5/18遞歸算法(c++實(shí)現(xiàn))
2.C++程序如下：#include<cstdio>intGCD(inta,intb){returna%b?gcd(b,a%b):b;}intmain(){intx,y;scanf("%d%d",&x,&y);printf("%d",GCD(x,y));return0;}3.輾轉(zhuǎn)相除法(Matlab實(shí)現(xiàn))functionGCD=Euclid(m,n)%輾轉(zhuǎn)相除法(即歐幾里德算法)。r=mod(m,n);whiler~=0r=mod(m,n);m=n;n=r;endGCD=m;>>m=319;n=377;Euclid(m,n)ans=29
4.遞歸算法（Python實(shí)現(xiàn)）defgcd(n1,n2):"""greatestcommondivisorfunction"""if(n1%n2==0):returnn2returngcd(n2,n1%n2)
最大公約數(shù)相關(guān)的文章
《娜娜》（英語(yǔ)：Nana）改編自矢澤愛(ài)的同名漫畫(huà)，由大谷健太郎執(zhí)導(dǎo)，矢澤愛(ài)、淺野妙子編劇，中島美嘉、宮崎葵、松田龍平等人主演的日本音樂(lè)、劇情電影，于2005年9月3日在日本上映。
明道大學(xué)（MINGDAO UNIVERSITY），前身是汪廣平2001年創(chuàng)立的明道管理學(xué)院，位于中國(guó)臺(tái)灣彰化縣埤頭鄉(xiāng)文化路369號(hào)。于2007年更名為明道大學(xué)，首屆海青班入學(xué)。2020年明道大學(xué)通過(guò)美國(guó)國(guó)際獨(dú)立院校認(rèn)證委員會(huì)（ACICS）認(rèn)證。至2023年6月23日校長(zhǎng)為郭秋勛。
世界氣象組織（英語(yǔ)全稱(chēng)：World Meteorological Organization，簡(jiǎn)稱(chēng)：WMO），是聯(lián)合國(guó)的一個(gè)專(zhuān)門(mén)機(jī)構(gòu)，總部設(shè)于瑞士日內(nèi)瓦，有193個(gè)會(huì)員國(guó)和會(huì)員地區(qū)（截至2023年6月） ，致力于在地球大氣狀態(tài)和變化規(guī)律及其與陸地和海洋的相互作用、大氣產(chǎn)生的天氣和氣候、以及由此產(chǎn)生的水
炒飯是常見(jiàn)的一種食物，分為多種品類(lèi)，如揚(yáng)州炒飯、香腸炒飯、西紅柿炒飯、咖喱炒飯、培根炒飯等，很受大眾追捧，在各個(gè)地方特色化。主要材料是用煮好的米飯、一些菜肴、雞蛋爆炒而成。一般大眾把炒飯當(dāng)做早飯或者是晚飯，因?yàn)槌达堉谱鞣奖悖臅r(shí)較少。
里斯本（葡萄牙語(yǔ)：Lisboa、英語(yǔ)：Lisbon），是葡萄牙共和國(guó)的首都。位于該國(guó)西部，城北為辛特拉山，城南臨塔古斯河，距離大西洋不到12公里，是歐洲大陸最西端的城市，也是南歐著名的都市之一。里斯本是工業(yè)城市、國(guó)際化都市，如今是葡萄牙的政治、經(jīng)濟(jì)、文化、教育中心，亦是歐洲著名的旅游城市，每年接待游
尚可名片
這家伙太懶了，什么都沒(méi)寫(xiě)！
作者
