一、最大公约数(Greatest Common Divisor)
几个自然数，公有的因数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数。例如：12、16的公约数有1、2、4，其中最大的一个是4，4是12与16的最大公约数，一般记为（12、16）=4。12、15、18的最大公约数是3，记为（12、15、18）=3。
二、编程求两个数的最大公约数
求最大公约数有多种方法，没有专门学过方法的人，首先可能会联想到穷举法。
（一）穷举法
#include <stdio.h>
// 穷举法
int gcd(int num1, int num2)
{
// 求最小的那个数
int divisor = num1 < num2 ? num1 : num2;
for(; divisor >= 1; divisor--)
{
if(0 == num1 % divisor && 0 == num2 % divisor)
{
// 找到最大公约数，跳出循环
break;
}
}
return divisor;
}
int main()
{
printf("%d", gcd(12, 16));
return 0;
}
运行结果：
4
分析：
穷举法虽然简单，但是有一个很大的缺点，就是效率低。比如咱们输入10000和15000，那么程序是从10000开始自减，一直减到5000，才得出了结果。这个过程for共执行了10000-5000+1 = 5001次。
所以求最大公约数，通常不用穷举法。
那么有没有其他求最大公约数的方法呢？
有的。
常见的有辗转相除法、相减法、短除法等。
（二）辗转相除法
思路:
有两整数a和b
① a%b得余数c
② 若c=0，则b即为两数的最大公约数
③ 若c≠0，则a=b，b=c，再回去执行①
例子: a = 10000 b = 15000，则运算过程为
① c = a % b = 10000 % 15000 = 10000, a = b = 15000, b = c = 10000
② c = a % b = 15000 % 10000 = 5000, a = b = 10000, b = c = 5000
③ c = a % b = 10000 % 5000 = 0, 则b = 5000即为最大公约数
程序：
#include <stdio.h>
// 递归实现辗转相除法
int gcd(int a, int b)
{
if(0 == b)
{
return a;
}
return gcd(b, a% b);
}
int main()
{
printf("%d", gcd(10000, 15000));
return 0;
}
运行结果：
5000
分析：
与穷举法相比，求10000和15000的最大公约数，辗转相除法只循环了三次，就得到了结果。效率提高了很多。
可以将辗转相除法的代码简化成一行
int gcd(int a, int b)
{
return 0 == b ? a : gcd(b, a % b);
}
（三）相减法
又叫更相减损法、等值算法，起源于《九章算术》。
思路：
有两整数a和b
① 若a>b，则a = a - b
若a<b，则b = b - a
② 若a=b，则a（或b）即为两数的最大公约数
若a≠b，则再回去执行①
例子：求27和15的最大公约数过程为：
① a = a - b = 27－15＝12
② b = b - a = 15－12＝3
③ a = a - b = 12－3＝9
④ a = a - b = 9－3＝6
⑤ a = a - b = 6－3＝3，此时a = b = 3，则3即为所求。
程序：
#include <stdio.h>
// 相减法
int gcd(int num1, int num2)
{
while(num1 != num2)
{
if(num1 > num2)
{
num1 -= num2;
}
else
{
num2 -= num1;
}
}
return num1;
}
int main()
{
printf("%d", gcd(27, 15));
return 0;
}
运行结果：
3
（四）短除法
思路：
左边部分的因子相乘，即为最大公约数。
所以，12与16的最大公约数为2 * 2 = 4
程序：
#include <stdio.h>
// 短除法
int gcd(int m, int n)
{
int min = m < n ? m : n;
int s = 1;
int i;
for(i = 2; i <= min ; i++)
{
// 四个条件只要有一个不满足，while循环结束
while(m > 0 && n > 0 && 0 == m % i && 0 == n % i)
{
m /= i;
n /= i;
s *= i;
}
}
return s;
}
int main()
{
printf("%d", gcd(12, 16));
return 0;
}
运行结果：
4
三、作业
辗转相除法特别重要，必须掌握。其他三种方法了解思路即可。
想了解少儿编程、少儿英语请加微信307591841或QQ307591841
公众号.jpg
