C语言每日一练——Day01：求最大公约数(三种方法)

一、什么是公约数？

公约数，就是能同时整除几个整数的整数。最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。

例如： 2能整除4，2能整除8；4能整除4，4能整除8，所以说(2和4)是(4和6)的公约数，而4是(2和4)的最大公约数。

二、求解两个数的最大公约数

🍑1、枚举法

思路： 假设两个数字a和b，比较出更小的数字赋值给变量min，遍历1到min的整数，找到所有能共同被a和b整除的数字，其中数值最大的便是所求最大公约数。

📝代码展示

//枚举法
#include
int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d",&a,&b);
	int min = (a < b ? a : b);
	while (a % min != 0 || b % min != 0)//如果不能同时整除
	{
		min--;
	}
	printf("%d",min);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

🍑2、相减法

思路： 假设两个数字a和b，如果a>b，则a=a-b;如果b>a,则b=b-a。一直循环计算直到a=b，则此时a、b的值即为所求最大公约数。

📝代码展示：

//相减法
#include
int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d",&a,&b);
	while (a != b)//直到两个数相等
	{
		if (a > b)
		{
			a = a- b;
		}
		else
		{
			b = 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

🍑3、辗转相除法

思路： 假设两个数字a和b，求两个数字相除的余数c=a%b，如果余数为0，则b为最大公约数。如果b不为零，a=b,b=c,继续循环计算。

📝代码展示：

//辗转相除法
#include
int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d",&a,&b);
	while (a%b != 0)//如果不能整除
	{
		int c = a % b;
		a = b;
		b = c;
	}
	printf("%d",b);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

📖总结

• 三种方法穷举法效率最低
• 推荐使用辗转相除法和相减法