C语言求两个数的最大公约数的三种算法

1.相减法

#include<stdio.h>
//相减法 
int main()
{
	int a,b;
	int c=0;  //计数器 
	while(1)  //循环判断的作用 
	{
		printf("输入两个数字求最大公约数:");
		scanf("%d%d",&a,&b);
		while(a!=b)
		{
			if(a>b)
			  a=a-b;
			else
			  b=b-a;
			c++;
				}
		printf("最大公约数是:%d
",a);
	    printf("%d
",c);		
	}
	return 0;
 }

运行结果

输入两个数字求最大公约数:9 4
最大公约数是:1
5
输入两个数字求最大公约数:4 8
最大公约数是:4
6
输入两个数字求最大公约数:

理解：

两个数a,b;

(a>b) a=a-b;

a<b:

b=b-a;

两个数不断相减，循环截止条件是：a==b;也就是说，当a==b时，运行结束，此时的a或b的值就是最终结果

另外，代码里加入了计数器c,用来判断循环次数，下面的两种方法中也同样引入了计数器，这里就不在重复解释了；

2.穷举法

#include<stdio.h>
//穷举法 
int main()
{
	int a,b,c;
	int d=0;//计数器 
	while(1)
	{
		printf("输入两个数字求最大公约数:");
	    scanf("%d%d",&a,&b);
	    c=(a>b)?b:a;//三目运算符 
	    while(a%c!=0||b%c!=0) 
	    {
		   c--;
		   d++;
	    }
	    printf("最大公约数是:%d
",c);
	    printf("%d
",d);
	}
	return 0;
 }

运行结果

输入两个数字求最大公约数:3 4
最大公约数是:1
2
输入两个数字求最大公约数:6 4
最大公约数是:2
4
输入两个数字求最大公约数:

理解：

三个变量，a,b,c;

c=（a,b）两个变量中较小的那个.

然后a,b分别都与c相除，只要有一方不能被c整除，就继续循环，循环中c--，c逐次减少，直到a,b,都能同时被c整除，运行结束

这里我加入了三目运算符这个c语言算数概念，意思是c = (a>b)?b:a; ?是条件判断，?前面的是真还是假，为真的话，取b,假的话,取a;这句的意思是c取两个数的较小值

3.辗转相除法

# include <stdio.h>
//辗转相除法 
int main ()
{
	int a,b,c;
	int d=0;//计数器 
	while(1)
	{
		printf("输入两个数字求最大公约数：");
		scanf("%d%d",&a,&b);
		c = a%b;
		while(c!=0)
		{
			a=b;
			b=c;
			c=a%b;
			d++;
		}
		printf("最大公约数为：%d
",b);
		printf("%d
",d);
	}
	return 0;
}

运算结果

输入两个数字求最大公约数：4 3
最大公约数为：1
1
输入两个数字求最大公约数：6 4
最大公约数为：2
2
输入两个数字求最大公约数：

理解： 1.将两整数求余 a%b = c 2.如果c = 0;则b为最大公约数 3.如果c != 0,则 a = b；b = c；继续从1开始执行 4.也就是说该循环的是否继续的判断条件就是c是否为0

以上是我对这个问题的思考和思路，希望大家能多多鼓励，望与君共勉！！