C语言：最大公约数详解

C语言：最大公约数详解

Hello！小伙伴们大家好，几天不见了，今天给大家分享一下C语言中求最大公约数的三种方法。在开始分享前，让我们先来看看什么是最大公约数：最大公约数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。接下来，我们将为大家分享求最大公约数的三种不同的方法：

1.辗转相除法

同样的，加入x,y有最大公约数T,则x,y都可以被T整除。同时可以发现，如果我们同时给x,y分别乘以m,n他们依然可以被T整除，把两个数字相加或相减后上述情况任然成立，即C = mx +（±ny）,c可以被T整除。在数学中（假设x > y）x/y = a …b，则b = x - a * y;从这里我们可以得到b也可以被T整除 。因此我们总结出，如果对x,y进行取模运算，把结果赋值给大的一个数，在继续上述的步骤，继续取模运算，会使x,y的值不断的减小，直到两数相等时x%y == 0;这时，在循环中不为0的一个数就是x,y的最大公约数 。
流程图

代码

#include <stdio.h>
#include <windows.h>

#pragma warning(disable:4996)

int maxNum(int num1, int num2)
{
	while (num1 * num2 != 0)
	{
		if (num1 > num2)
		{
			num1 = num1 % num2;
		}
		else if (num1 < num2)
		{
			num2 = num2 % num1;
		}
		else
		{
			break;
		}
		return num1 == 0 ? num2 : num1;
	}
}
int main()
{
	int num1, num2;
	printf("请输入两个整数：");
	scanf("%d%d", &num1,&num2);
	int result = maxNum(num1,num2);
	printf("%d,%d的最大公约数是：%d\n", num1, num2, result);
	system("pause");
	return 0;
}

2.穷举法

顾名思义，就是运用循环，将两个数x，y中较小的值赋给i，将x除以i，y也除以i，若两者的余数同时为0时，此时的i就是两者的最大公约数。若不等于0，则将i-1，继续将x除以i，y除以i，直至余数同时为0。
流程图

代码：

#include <stdio.h>
#include <windows.h>

#pragma warning(disable:4996)

int maxNum(int num1, int num2)
{
	int i = 0;
	if (num1 > num2)
	{ 
		i = num2;
	}
	else
	{
		i = num1;
	}
	for (; i > 0; i--)
	{
		if (num1 % i == 0 && num2 % i == 0)
		{
			return i;
		}
	}
}
int main()
{
	int num1, num2;
	printf("请输入两个整数：");
	scanf("%d%d", &num1,&num2);
	int result = maxNum(num1,num2);
	printf("%d,%d的最大公约数是：%d\n", num1, num2, result);
	system("pause");
	return 0;
}

3.辗转相减法

为了让大家更容易的理解这个方法，我们先假设数字x,y的最大公约数为T，容易发现x = T + T +…+ T，y = T + T +…+ T，所以当我们用他们之间的大的一个数减去小的一个数时，x - y(或y - x)相当于是减少了T的个数，重复上述步骤，当x和y相等时即x - y (或 y-x)= 0时他们之间的T的个数相等，此时x = y = T;
流程图：

代码

#include <stdio.h>
#include <windows.h>

#pragma warning(disable:4996)

int maxNum(int num1, int num2)
{
	while (1)
	{
		if (num1 > num2)
		{
			num1 = num1 - num2;
		}
		else
		{
			num2 = num2 - num1;
		}
		if (0 == num1 - num2)
		{
			break;
		}
	}
	return num1;
}
int main()
{
	int num1, num2;
	printf("请输入两个整数：");
	scanf("%d%d", &num1,&num2);
	int result = maxNum(num1,num2);
	printf("%d,%d的最大公约数是：%d\n", num1, num2, result);
	system("pause");
	return 0;
}