目录
一、什么是最大公约数？二、求最大公约数的三种常用方法2.1. 辗转相除法（欧几里得算法）2.2. 辗转相减法（更相减损术）2.3. 枚举法
总结
一、什么是最大公约数？
公约数，亦称公因数，与公倍数相反，它是一个能同时整除若干整数的整数。如果一个整数同时是几个整数的约数，称这个整数为它们的“公约数”。公因数中最大的那个称为最大公约数。 例如，12和18的公约数有1、2、3、6，最大公约数就是6；30和40的公约数有1、2、5、10，最大公约数是10。
二、求最大公约数的三种常用方法
2.1. 辗转相除法（欧几里得算法）
首先将两个数进行模运算，即a%b ① 当a能被b整除时即 a%b == 0，直接返回 b ，b就是最大公约数。 例如，a=12，b=6，a%b=0，b=6就是这两个数的最大公约数。 ② 当a不能被b整除时 a%b != 0，则进行辗转相除。 用第三个变量来接收 a%b，即c = a%b，用 a 来接收 b的值，用 b 来接收 c 的值。 ③ 重复上述①和②
例如：
a = 6,b = 12; a%b != 0; c = a%b = 6; a = b = 12; b = c = 6; a%b = 12%6 = 0; 所以6和12最大公因数为 6
通俗一点，辗转相除：不能整除时，把a赋值为b，b赋值为a%b，直到可以整除为止。 c只是一个临时中间变量。
算法流程图 非递归代码实现
//求最大公约数 辗转相除法
int fun(int a, int b)
{
while (a % b != 0)
{
int c = a % b;
a = b;
b = c;
}
return b;
}
递归代码实现
int gcd(int a, int b)
{
if(a%b == 0)
return b;
else
return gcd(b,a%b);
}
2.2. 辗转相减法（更相减损术）
更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。
原文：
可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。
翻译：
第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简； 若不是则执行第二步。 第二步：把较大的数减较小的数，将所得的差与较小的数比较，并以大数减小数。重复这个操作，直到所得的减数和差相等为止。 第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。
编写代码时运用提取上述第二步的思想最为简便，例如：
a = 12,b = 18; b > a; b = b - a = 6; a > b; a = a - b = 6; a = b = 6; 所以6和12最大公因数为 6
通俗一点，辗转相减：不相等时，大的那个赋值为大 - 小，直到相等为止。
代码实现
//求最大公约数 辗转相减法
int fun(int a, int b)
{
while(a != b)
{
if(a > b)
a = a-b;
if(b > a)
b = b-a;
}
return a;
}
2.3. 枚举法
最暴力无脑的方法，直接从a、b中小的那个开始一个一个往下找。
代码展示
//枚举法
int fun(int a, int b)
{
int tmp;
if(a <= b) tmp = a;
else tmp = b;
while(tmp)
{
if(a%tmp == 0 && b%tmp == 0)
break;
tmp --;
}
return tmp;
}
总结
这篇文章学习了求最大公约数的三种常用方法：辗转相除法、辗转相减法、枚举法。