【C语言刷题每日一题】——求最大公约数（带数学计算过程详解）

概念介绍

最大公约数——两个整数中公共约数（因数）的最大者

求最大公约数的方法有很多，如质数因数分解法、短除法、辗转相除法、更相减损法。

这里介绍使用代码实现求最大公约数的最简单的一种方法——辗转相除法

辗转相除法 数学思想介绍

求最大公约数过程——

比如有两个数，18和24

第一步：用第一个数18作为被除数，第二个数24作为除数，两个数做除法，并求余数

18%24=18，余数为18

第二步：再将上一次计算中的除数作为被除数，余数作为除数，再进行除法运算求余数

24%18=6

第三步：重复上一次操作

再将上一次计算中的除数作为被除数，余数作为除数，再进行除法运算求余数

18%6=0

一直进行求余数操作，直到余数为0时，这时的除数就是初始两个数的最大公约数

注意：不管两个数谁大谁小，只要按此过程就可以得到最大公约数

图解演示

代码思路

要实现求两个数的最大公约数，明白了数学逻辑，实现就变得很简单

1. 创建两个整型变量存储键盘输入的数据
2. scanf函数读入数据（如果是多组输入的话，使用while循环读入数据）
3. 求最大公约数的过程用一个循环来实现，余数为0就是循环结束的条件，在每一次循环过程中完成除数和被除数的调整

代码实现

#include<stdio.h>
int main()
{
	int a = 0, b = 0;
	while (scanf("%d %d", &a, &b) != EOF)
	{
		int c = 0;//用于临时存储余数
		while (c = a % b)//当余数不为0时，进行循环
		{
			a = b;//除数变为被除数
			b = c;//余数变为除数
		}
		printf("最大公约数为%d\n", b);
	}

}

代码改进

如果你仔细观察上面实现的这段代码的话，就会发现，最初我们输入的两个值在经过计算后被破坏了，计算完成之后就无法再使用初始的值

所以，我们将代码进行一下改进，每次用两个临时变量来拷贝输入的值，然后进行运算的时候只对临时拷贝的值进行操作，初始的两个值就被保留了下来。这样一个微不足道的小细节对于我们养成保持数据的安全和一致性是一个好习惯

#include<stdio.h>
int main()
{
	int a = 0, b = 0;
	while (scanf("%d %d", &a, &b) != EOF)
	{
		int c = 0;//用于临时存储余数
		int temp1 = a, temp2 = b;//拷贝要进行运算的两个整数
		while (c = temp1 % temp2)//当余数不为0时，进行循环
		{
			temp1 = temp2;//除数变为被除数
			temp2 = c;//余数变为除数
		}
		printf("%d和%d的最大公约数为%d\n", a,b,temp2);
	}

}

效果展示