C语言求最大公约数代码

题目：随机输入两个数，求其最大公约数

在此展示三种常用解题思路 1.首先展示第一种思路

#include <stdio.h>
 int main()
{
          
   
	int a,b,c;             //先定义变量
	printf("请输入：
");
	scanf("%d%d",&a,&b);   //输入两个整型数字
	if(a<b)               
	{
          
   
		c=a;
		a=b;
		b=c;               //保证a≥b
	}
	int i = 0;
	for(i = b;i>0;i--)
	{
          
   
		if(a%i == 0 && b%i == 0)                
		{
          
   
			printf("gcd(%d,%d) = %d
",a,b,i);
			break;
		}
	}
	return 0;
}

2.辗转相除法 这里涉及到一个公式：GCD(a,b) = GCD(b,a%b)

#include <stdio.h>
int main()
{
          
   
	int a,b,c;
	printf("请输入：");
	scanf("%d%d",&a,&b);
	if(a<b)
	{
          
   
		c = a;
		a = b;
		b = c;                      //确保a≥b
	}
	while(b != 0)                   
	{
          
   	
		c = b;
		b = a%b;                    //辗转相除：相比第一种思路大大提高了代码的效率
		a = c;
	}
	printf("最大公约数为：%d",a);
	return 0;
}

还有一种运用递归的思想

#include <stdio.h>
int Gcd(int a,int b)
{
          
   
	if(a > b)
	{
          
   
		if(a % b == 0)
		{
          
   
			return b;
		}
		else
		{
          
   
			return Gcd(b,a%b);    
		}
	}
	else
	{
          
   
		if(b % a == 0)
		{
          
   
			return a;
		}
		else
		{
          
   
			return Gcd(a,b%a);
		}
	}
}
int main()
{
          
   
	int a, b;
	int c = 0;
	printf("请输入两个整数：");
	scanf("%d%d",&a, &b);
	c = Gcd(a, b);
	printf("GCD（%d,%d）=%d
",a,b,c);
}

3.更相减损术 定义：(如果需要对分数进行约分，那么)可以折半的话，就折半(也就是用2来约分)。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。

#include <stdio.h>
main()
{
          
   
	int a,b;
	printf("请输入两个正整数：");
	scanf("%d%d",&a,&b);
	while(a%2==0)
	{
          
   
		a/=2;
	}
	while(b%2==0)
	{
          
   
		b/=2;
	}               //让两个数都为奇数
	while(a!=b)
	{
          
   
		if(a>b) a=a-b;               
		else b=b-a;              //更相减损术：当差值等于减数的值时即为最大公约数
	}
	printf("GCD=%d
",a);
	return 0;
}

本文结束，感谢阅览！