C語(yǔ)言最大公約數(shù)的示例分析

今天就跟大家聊聊有關(guān)C語(yǔ)言最大公約數(shù)的示例分析，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

窮舉法

（1） i= a ，b中較小的數(shù)
（2）若a，b能同時(shí)被i整除，則i即為最大公約數(shù)，結(jié)束
（3）若不能，則 i--，再回去執(zhí)行（2）

#include<stdio.h>
int main()
{
	int i = 0;
	int j = 0;
	scanf("%d %d", &i, &j);
	int k = i > j ? i : j;//i>j,k=i;i<j,k=j
	while(1)
	{
		if (i%k == 0 && j%k == 0)
		{
			printf("最大公約數(shù)為；%d\n", k);
			break;
		}
		k--;
	}
	return 0;
}

 輾轉(zhuǎn)相除法

輾轉(zhuǎn)相除法求兩個(gè)數(shù)的最大公約數(shù)的步驟如下：
（1）先用小的一個(gè)數(shù)除大的一個(gè)數(shù)，得第一個(gè)余數(shù)；
（2）再用第一個(gè)余數(shù)除小的一個(gè)數(shù)，得第二個(gè)余數(shù)；
（3）又用第二個(gè)余數(shù)除第一個(gè)余數(shù)，得第三個(gè)余數(shù)；
這樣逐次用后一個(gè)數(shù)去除前一個(gè)余數(shù)，直到余數(shù)是0為止。那么，最后一個(gè)除數(shù)就是所求的最大公約數(shù)。

#include<stdio.h>
int main()
{
	int a = 0;
	int b = 0;
	int c = 0;
	scanf("%d %d", &a, &b);
	while (c = a%b)
	{
		a = b;
		b = c;
	}
	printf("%d\n", b);
	return 0;
}

 輾轉(zhuǎn)相減法

兩整數(shù)a和b：
（1） 若a>b，則a=a-b
（2）若a<b，則b=b-a
（3） 若a=b，則a（或b）即為兩數(shù)的最大公約數(shù)，結(jié)束
（4）若a≠b，則再回去執(zhí)行（1）

#include<stdio.h>
int main()
{
	int a = 0;
	int b = 0;
	scanf("%d%d", &a, &b);
	int ret = 0;
	while (1)
	{
		if (a < b)
		{
			int tmp = 0;
			tmp = a;
			a = b;
			b = tmp;
		}
		ret = a - b;
		if (ret == b)//判斷
		{
			printf("ret = %d", ret);
			break;
		}
		else//交換
		{
			a = b;
			b = ret;
		}
	}
	return 0;
}

看完上述內(nèi)容，你們對(duì)C語(yǔ)言最大公約數(shù)的示例分析有進(jìn)一步的了解嗎？如果還想了解更多知識(shí)或者相關(guān)內(nèi)容，請(qǐng)關(guān)注億速云行業(yè)資訊頻道，感謝大家的支持。