目錄
前言
一、枚舉法
二、輾轉(zhuǎn)相除法
三、更相減損法
前言
如何求兩個(gè)數(shù)的最大公約數(shù)是非常經(jīng)典的問(wèn)題，求解的方法也有很多，本文主要介紹其中的三種方法，分別是：枚舉法、輾轉(zhuǎn)相除法和更相減損法。
?
一、枚舉法
兩個(gè)數(shù)的最大公約數(shù)一定小于或等于兩數(shù)中較小的數(shù)，并且這兩個(gè)數(shù)必定至少存在一個(gè)公因數(shù) 1，利用這兩個(gè)條件，可以將兩個(gè)數(shù)的最大公約數(shù)的所有可能都列舉出來(lái)。
#include <stdio.h>
int main()
{
int a = 0;
int b = 0;
int min = 0;
scanf("%d%d", &a, &b);
if (a > b)
min = b;
else
min = a;
for (int i = min; i > 0; i--) // i：min -> 1
{
if (a % i == 0 && b % i == 0)
{
printf("的最大公約數(shù)為 %d", i);
break;
}
}
return 0;
}二、輾轉(zhuǎn)相除法
輾轉(zhuǎn)相除法，又名歐幾里得算法，是求最大公約數(shù)的一種算法。輾轉(zhuǎn)相除法首次出現(xiàn)于歐幾里得的《幾何原本》中的第 Ⅶ 卷，書(shū)中的命題 i 和命題 ii 所描述的就是輾轉(zhuǎn)相除法。
輾轉(zhuǎn)相除法的本質(zhì)就是：用一個(gè)數(shù)除以另一個(gè)數(shù)，如果余數(shù)不為 0，則用除數(shù)除以余數(shù)，一直反復(fù)，直到余數(shù)為 0 為止，即 a % b = r1，若 r1 ≠ 0，則用 b % r1 = r2，若 r2 ≠ 0，那么一直反復(fù)，直到某個(gè)余數(shù) rn 為0 為止，最后一條式子的除數(shù)就是兩個(gè)數(shù)的最大公約數(shù)。
把兩個(gè)數(shù)看作被除數(shù)與除數(shù)的關(guān)系，則兩個(gè)數(shù)的最大公約數(shù)就等于除數(shù)與余數(shù)的最大公約數(shù)，即 gcd(a, b) = gcd(b, r)。
輾轉(zhuǎn)相除法源于希臘，希臘人非常喜歡從圖形或者是用幾何的角度去看待問(wèn)題，很多希臘數(shù)學(xué)家都習(xí)慣先去思考能否將其轉(zhuǎn)換為直觀的幾何圖形再進(jìn)行求解。所以很自然地，希臘數(shù)學(xué)家在面對(duì)求兩個(gè)數(shù)的最大公約數(shù)這個(gè)問(wèn)題時(shí)，也首先去思考這個(gè)問(wèn)題是否能通過(guò)將其轉(zhuǎn)換成一個(gè)幾何問(wèn)題來(lái)處理。在經(jīng)過(guò)一些嘗試之后，這一設(shè)想最終實(shí)現(xiàn)了，希臘數(shù)學(xué)家將所要求最大公約數(shù)的兩個(gè)數(shù)字 a 和 b 分別作為矩形的兩條邊，那么這個(gè)問(wèn)題就被轉(zhuǎn)換成在這個(gè)矩形中找到這樣一個(gè)正方形，這個(gè)正方形能夠沒(méi)有縫隙地鋪滿(mǎn)上述矩形，顯然這類(lèi)正方形可能有多個(gè)（當(dāng)然，也只考慮正整數(shù)邊長(zhǎng)的正方形），而我們的目標(biāo)就是找出這類(lèi)正方形中最大的那一個(gè)。
那么我們?nèi)绾握业竭@樣一個(gè)正方形呢？具體操作如下：
證明：我們假設(shè) a = 16，b = 6，兩個(gè)數(shù)的最大公約數(shù)為 c。
顯然 c <= b，因此我們先用矩形的短邊 b 構(gòu)造正方形，然后判斷這樣的正方形能否鋪滿(mǎn)整個(gè)矩形，判斷方式可以是計(jì)算兩個(gè)數(shù)的余數(shù)。因?yàn)?a ÷ b = n ... r，余數(shù) r 不為零，所以 c ≠ b。又因?yàn)?a = k1c，b = k2c，r = a - n·b = k1c - nk2c = (k1 - nk2)c，所以 c 也是余數(shù) r 的約數(shù)，那么 c <= r，因此再用余數(shù) r 構(gòu)造正方形，判斷這樣的正方形能否鋪滿(mǎn)以 b 和 r 為邊的小矩形，即計(jì)算 b % r 的結(jié)果。
用余數(shù) r 構(gòu)造的正方形如果能鋪滿(mǎn)以 b 和 r 邊的小矩形，則一定能鋪滿(mǎn)整個(gè)大矩形。
一直反復(fù)，直到余數(shù)為 0 為止，最后能鋪滿(mǎn)矩形的正方形的邊長(zhǎng)就是 a 和 b 的最大公約數(shù)。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-404441.html
#include <stdio.h>
int main()
{
int a = 0;
int b = 0;
int r = 0;
scanf("%d%d", &a, &b);
while ((r = a % b) != 0)
{
// 若余數(shù)不為 0
a = b;
b = r;
}
// 當(dāng)余數(shù)為 0 時(shí)，除數(shù)就是兩數(shù)的最大公約數(shù)
printf("最大公約數(shù)是 %d\n", b);
return 0;
}三、更相減損法
更相減損術(shù)是出自《九章算術(shù)》的一種求最大公約數(shù)的算法，其本質(zhì)是：以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小數(shù)相比較，并以較大數(shù)減較小數(shù)，繼續(xù)這樣的操作，直到所得的減數(shù)和差相等為止，即若 a > b，a - b = s1（s1 ≠ 0），若 b > s1，b - s1 = s2（s2 ≠ 0），若 s1 = s2，s1 - s2 = 0，那么 s1、s2 就是 a 、b 的最大公約數(shù)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-404441.html
#include <stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d%d", &a, &b);
while (a != b)
{
if (a > b)
a -= b; // 當(dāng) a > b 時(shí)，a 來(lái)保存兩數(shù)的差
else
b -= a; // 當(dāng) a < b 時(shí)，b 來(lái)保存兩數(shù)的差
}
printf("最大公約數(shù)是 %d", a);
return 0;
}到了這里，關(guān)于你會(huì)求兩個(gè)數(shù)的最大公約數(shù)嗎（三種方法）？的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
