如何求解最大公約數(shù)，首先了解什么是最大公約數(shù)，如果有一個(gè)自然數(shù)a能被自然數(shù)b整除，則稱a為b的倍數(shù)，b為a的約數(shù)。幾個(gè)自然數(shù)公有的約數(shù)，叫做這幾個(gè)自然數(shù)的公約數(shù)。公約數(shù)中最大的一個(gè)公約數(shù)，稱為這幾個(gè)自然數(shù)的最大公約數(shù)。

例： 在2、4、6中，2就是2，4，6的最大公約數(shù)。

再C語(yǔ)言中，有以下三種求法：

方法一：

int main() {
	int a;
	int b;
	printf("請(qǐng)輸入兩個(gè)正整數(shù)：");
	scanf("%d %d", &a, &b);
	int i = 0;
	int m = 0;
	for (i = 1; i <= a && i <= b; i++) {
		if (a % i == 0 && b % i == 0) {
			m = i;
		}
	}
	printf("最大公約數(shù)為:%d\n", m);
		return 0;
}

?該方法是將兩個(gè)數(shù)依次對(duì)1開(kāi)始取模，往后++，直到滿足兩個(gè)都對(duì)i取模為0結(jié)束。

方法二：

int main() {
	int a;
	int b;
	printf("請(qǐng)輸入兩個(gè)正整數(shù)：");
	scanf("%d %d", &a, &b);
	//找到兩個(gè)數(shù)的較小者
	int min = (a < b ? a : b);
	while (1) {
		if (a % min == 0 && b % min == 0) {
			break;
		}
		min--;
	}
	printf("最大公約數(shù)為:%d\n", min);
	return 0;
}

?該方法是找到兩個(gè)數(shù)的較小者，輸入的兩個(gè)數(shù)依次對(duì)較小者取模，滿足上述條件結(jié)束。

?方法三：

//輾轉(zhuǎn)相除法
int main() {
	int a;
	int b;
	printf("請(qǐng)輸入兩個(gè)正整數(shù)：");
	scanf("%d %d", &a, &b);
	int k = 0;
	while (k = a % b) {
		a = b;
		b = k;
	}
	printf("最大公約數(shù)為:%d\n", b);
	return 0;
}

?輾轉(zhuǎn)相除法一般指歐幾里得算法。歐幾里得算法又稱輾轉(zhuǎn)相除法，是指用于計(jì)算兩個(gè)非負(fù)整數(shù)a，b的最大公約數(shù)。那么輾轉(zhuǎn)相除法的原理是什么？

1、 原理：設(shè)兩數(shù)為a、b(ab)，用gcd(a，b)表示a，b的最大公約數(shù)，r=a(mod b)為a除以b的余數(shù)，k為a除以b的商，即a÷b=k。。。。。。。r。輾轉(zhuǎn)相除法即是要證明gcd(a，b)=gcd(b，r)。

2、 第一步：令c=gcd(a，b)，則設(shè)a=mc，b=nc。

3、 第二步：根據(jù)前提可知r=a-kb=mc-knc=(m-kn)c。

4、 第三步：根據(jù)第二步結(jié)果可知c也是r的因數(shù)。

5、 第四步：可以斷定m-kn與n互質(zhì)(假設(shè)m-kn=xd，n=yd(d1)，則m=kn+xd=kyd+xd=(ky+x)d，則a=mc=(ky+x)cd，b=nc=ycd，則a與b的一個(gè)公約數(shù)cdc，故c非a與b的最大公約數(shù)，與前面結(jié)論矛盾)，因此c也是b與r的最大公約數(shù)。

6、 從而可知gcd(b，r)=c，繼而gcd(a，b)=gcd(b，r)。

7、 證畢。以上步驟的操作是建立在剛開(kāi)始時(shí)r≠0的基礎(chǔ)之上的。即m與n亦互質(zhì)。

8、 解釋：輾轉(zhuǎn)相除法，又名歐幾里德算法（Euclidean algorithm）乃求兩個(gè)正整數(shù)之最大公因子的算法。它是已知最古老的算法，其可追溯至公元前300年前。

9、 來(lái)源：設(shè)兩數(shù)為a、b(ab)，求a和b最大公約數(shù)(a，b)的步驟如下：用a除以b，得a÷b=q。。。。。。r1(0≤r1)。若r1=0，則(a，b)=b；若r1≠0，則再用b除以r1，得b÷r1=q。。。。。。r2(0≤r2）。若r2=0，則(a，b)=r1，若r2≠0，則繼續(xù)用r1除以r2，……如此下去，直到能整除為止。其最后一個(gè)余數(shù)為0的除數(shù)即為(a， b)的最大公約數(shù)。

10、 例如：a=25，b=15，a/b=1。。。。。.10，b/10=1。。。。。.5，10/5=2。。。。。。.0，最后一個(gè)余數(shù)為0d的除數(shù)就是5， 5就是所求最大公約數(shù)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-434375.html

“只有兩種編程語(yǔ)言：大家抱怨的和沒(méi)人用的?！薄举Z尼·斯特勞斯特魯普（Bjarne Stroustrup）

到了這里，關(guān)于最大公約數(shù)的三種求法——（C語(yǔ)言）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！