C语言最大公约数示例教程

沃梦达教程 C/C++开发

2023-01-05 14

这篇文章主要为大家介绍了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;
}