求最大公约数的几种常见方法（C语言）

1.欧几里得算法(辗转相除法）

#define _CRT_SECURE_NO_WARNINGS 1
#include 

int gcd(int a, int b)
{
	if (b == 0)
	{
		return a;
	}
	else if (a == 0)
	{
		return b;
	}
	else
	{
		return gcd(b, a % b);
	}
}
int main()
{
	int a, b;
	printf("请输入两个数：n");
	scanf("%d %d", &a, &b);
	printf("最后的结果是：%d", gcd(a, b));
}

2.更相减术法：最常见的求解公约数的方法：将两数相减，：先判断两个数是否相等，若两数相等，则其最大公约数为其本身；若两数不等，则最差，然后用这个较小数与他们之间的差值进行比较，如果相等，则该差值就是其最大公约数，如果不等，则继续执行该比较与减法操作，直到最小数与差值相等为止。

#define _CRT_SECURE_NO_WARNINGS 1
#include 
int gcd(int a, int b)
{
	while (true)
	{
		if (a > b)
		{
			a = a - b;
		}
		else if (b > a)
		{
			b = b - a;
		}
		else
		{
			return a;//如果两数相等，则返回最小值(该数也是最大公约数)
		}
	}
}
int main()
{
	int a, b;
	printf("请输入两个数：n");
	scanf("%d %d", &a, &b);
	printf("最后的结果是：%d", gcd(a, b));
}

3.stein算法（结合辗转相除法以及更相减术法的优势，以及移位运算得到）

#define _CRT_SECURE_NO_WARNINGS 1
#include 
int gcd(int a, int b)
{
	if (a == 0)
	{
		return b;
	}
	if (b == 0)
	{
		return a;
	}
	if (a % 2 == 0 && b % 2 == 0)
	{
		return 2 * gcd(a >> 1, b >> 2);
	}
	else if (a % 2 == 0)
	{
		return (a >> 1, b);
	}
	else if (b % 2 == 0)
	{
		return(a, b >> 1);
	}
}
int main()
{
	int a, b;
	printf("请输入两个数：n");
	scanf("%d %d", &a, &b);
	printf("最后的结果是：%d", gcd(a, b));
}