一、最大公约数(Greatest Common Divisor)

几个自然数，公有的因数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数。例如：18、12的公约数有1、2、3、6，其中最大的一个是6，6是18与12的最大公约数，一般记为（18、12）=6。

二、编程求最大公约数

用c++编程实现，输入任意两个自然数a和b，求他们的最大公约数。
这个题目主要是考察小朋友们对循环的使用。

三、算法求解

1.穷举法

解析

穷举法是大部分人最先想到的方法。让一个数循环的去被a和b除，如果余数都为0那么就是他们的公约数，然后最大的那个就是最大公约数。

代码

#include <iostream>
using namespace std;

//穷举法
int gcd1(int a, int b)
{
    int x=(a<b?a:b);
    int z = 0 ,count=0;
    for(;x>0;x--)
    {
        if( a%x == 0 && b%x == 0 ){
            z=x;
            break;
        }
        count++;
    }
    cout<<"循环次数(穷举法)："<<count<<endl;
    return z;
}

int main(){
    int a,b,result;
    cin>>a>>b;
    result = gcd1(a,b);
    cout<<a<<"和"<<b<<"的最大公约数："<<result<<endl;
    return 0;
}

运行结果：

18 12
循环次数(穷举法)：6
18和12的最大公约数：6

分析

穷举法虽然简单，但是有一个很大的缺点，就是效率低。比如咱们输入1200和1800，那么程序是从1200开始自减，一直减到600，才得出了结果。这个过程for共执行了600次。含有很多小朋友会从1开始写自增，那么循环的次数就更多了。
所以求最大公约数，通常不用穷举法。
穷举法的效率极其的低下，和后面其他几个不在一个数量级上。

2.辗转相除法

解析

辗转相除法，又称欧几里得算法。用于计算两个正整数a，b的最大公约数和最小公倍数，其依赖于gcd(a,b) = a (b=0)和gcd(b,a mod b) (b!=0)。算法的具体描述如下图：

辗转相除法图示

代码

#include <iostream>
using namespace std;

//迭代相除法
int gcd2(int a, int b)
{
    int z = b;
    int count = 0;
    while (a % b != 0) {
        z = a % b;
        a = b;
        b = z;
        count++;
    }
    cout<<"循环次数(迭代相除)："<<count<<endl;
    return z;
}

int main(){
    int a,b,result;
    cin>>a>>b;
    result = gcd2(a,b);
    cout<<a<<"和"<<b<<"的最大公约数："<<result<<endl;
    return 0;
}

运行结果：

18 12
循环次数(迭代相除)：1
18和12的最大公约数：6

分析

可以看到迭代相除只用了一次循环就得到了结果，大大提高了效率。
此方法当数据较小的时候性能最好，代码可读性极好，但是它需要用到取余运算.

扩展

小朋友们只学到了循环，如果学到函数以及递归则可以把函数写成如下这样，大大简化代码提高可读性。

int gcd(int a, int b)
{
    return 0 == b ? a : gcd(b, a % b);
}

3.更相减损法

解析

更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。
《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，原文是：
可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。
白话文译文：
（如果需要对分数进行约分，那么）可以折半的话，就折半（也就是用2来约分）。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。
算法的图示如下：

更相减损法

代码

#include <iostream>
using namespace std;

//更相减损法
int gcd3(int a,int b)
{
    int count = 0;
    while(a != b)
    {
        if(a>b)
        {
            a = a - b;
        }
        else
        {
            b = b - a;
        }
        count++;
    }
    cout<<"循环次数(更相减损法)："<<count<<endl;
    return a;
}

int main(){
    int a,b,result;
    cin>>a>>b;
    result = gcd3(a,b);
    cout<<a<<"和"<<b<<"的最大公约数："<<result<<endl;
    return 0;
}

运行结果：

18 12
循环次数(更相减损法)：2
18和12的最大公约数：6

分析

可以看到更相减损法用了两次循环得到结果，效率也挺高，还有它不需要取余。
这种方法在计算大数的情况下依旧可以保持较快的速度，代码的可读性也非常高，但是因为要不断互减,在两个数较为接近的时候需要的系统资源较大。

4.短除法

解析

短除法应该是小朋友最熟悉的数学方法，和计算数学题时常采用的方法一致。

短除法

左边部分的因子相乘，即为最大公约数。
所以，18与12的最大公约数为2 * 3 = 6

// 短除法
int gcd4(int a, int b)
{
    int min = a < b ? a : b;
    int s = 1;
    int i;
    for(i = 2; i <= min ; i++)
    {
        // 四个条件只要有一个不满足，while循环结束
        while(a > 0 && b > 0 && 0 == a % i && 0 == b % i)
        {
            a /= i;
            b /= i;
            s *= i;
        }
    }
    return s;
}

int main(){
    int a,b,result;
    cin>>a>>b;
    result = gcd4(a,b);
    cout<<a<<"和"<<b<<"的最大公约数："<<result<<endl;
    return 0;
}

分析

短除法的效率也还算可以，它更多是和我们常用的数学方法一致，算法上比较容易理解，但是代码的可读性就比较差一些。