一、最大公约数(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;
}

运行结果：

分析：
穷举法虽然简单，但是有一个很大的缺点，就是效率低。比如咱们输入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;
}

运行结果：

分析：
与穷举法相比，求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;

}

运行结果：

（四）短除法

思路：

1.png

左边部分的因子相乘，即为最大公约数。
所以，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;
}

运行结果：