C語言最大公約數的示例分析

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

窮舉法

（1） i= a ，b中較小的數
（2）若a，b能同時被i整除，則i即為最大公約數，結束
（3）若不能，則 i--，再回去執行（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("最大公約數為；%d\n", k);
			break;
		}
		k--;
	}
	return 0;
}

 輾轉相除法

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

#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;
}

 輾轉相減法

兩整數a和b：
（1） 若a>b，則a=a-b
（2）若a<b，則b=b-a
（3） 若a=b，則a（或b）即為兩數的最大公約數，結束
（4）若a≠b，則再回去執行（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;
}

看完上述內容，你們對C語言最大公約數的示例分析有進一步的了解嗎？如果還想了解更多知識或者相關內容，請關注億速云行業資訊頻道，感謝大家的支持。