C语言第二十弹--求最大公因数

求最大公因数

最大公因数：也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。

一、穷举法

思路：找到两个数之间的最少值 使用第三接收最小值，然后通过判断两者%n是否同时等于0，同时为0证明就是两者的最大公因数，不是就n–继续判断。

#define _CRT_SECURE_NO_WARNINGS
#include c


int main()
{
	//穷举法
	int a = 0;
	int b = 0;
	scanf("%d %d",&a,&b);
	int n = a > b ? b : a;//获取最小值
	while (a % n != 0 || b % n != 0)//作为判断条件
	{
		n--;
	}
	printf("%d",n);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

二、辗转相除法

思路：两个数通过反复求模 获取到一个值，当两个数取模时值为0时证明该被取模的数就是两数的最大公因数。

例如 a = 24 b = 16 a % b = 8 此时a = 8,b = 16, 再次循环 b % a == 0 ,那么就证明a为最大公因数。需要注意的是 必须是大的数取余小的数 就需要进行判断。

总代码

#define _CRT_SECURE_NO_WARNINGS
#include 

int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d",&a,&b);
	while (a && b)
	{
		if (a > b)
		{
			a %= b;
		}
		else
		{
			b %= a;
		}
	}

	printf("%d",a > b ? a : b);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

三、更相相损法

思路：两数通过不断相损(相减)，当两者相等时，就是最大公因数。

例如 a = 24 b = 16,通过条件判断使 a -= b,那么此时a = 8 ,b = 16,再次进行条件判断 从而使 a = b，获得最大公因数。

总代码

#define _CRT_SECURE_NO_WARNINGS
#include 

int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d",&a,&b);
	while (a != b)
	{
		if (a > b)
		{
			a -= b;
		}
		else
		{
			b -= a;
		}
	}

	printf("%d",a);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23