最大公约数(gcd)

· · 个人记录

最大公约数（greatest common divisor，简写为 gcd ；或highest common factor，简写为hcf)，指某几个整数共有因子中最大的一个。

（1）更相减损术

注意，更相减损术算法的耗时长，一般不推荐使用。

更相减损术百度百科

代码如下：

非递归形式
int gcd(int a, int b)
{
    while (a != b)
    {
        if (a > b)a -= b;
        else b -= a;
    }
    return a;
}
递归形式

这个gcd函数在正int型内完全通用，返回a,b的最大公约数 但是当a,b之间差距较大时（如100000倍）会导致错误（栈过深）

int gcd(int a, int b)
{
    if (a == b)return a;
    else if (a > b)a -= b;
    else b -= a;
    return gcd(a, b);
}

（2）辗转相除法（欧几里得算法）

求最大公约数，一般都会使用此算法。

欧几里得算法百度百科

代码如下：

非递归形式：
int gcd(int a, int b)
{
    int temp = b;
    while (a % b)
    {   //辗转相除
        temp = a % b;
        a = b;
        b = temp;
    }
    return temp;
}
递归形式一：
int gcd(int a, int b)
{
    if (a % b == 0) return b;
    else return gcd(b, a % b);
}
递归形式二：
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

（3）求多个数的最大公约数

我们可以先求出前两个数的最大公约数(a)，再用这个最大公约数(a)与下一个数求出它们的最大公约数(b)，不断循环直到计算完所有数。

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
    if (a % b == 0) return b;
    else return gcd(b, a % b);
}

int main()
{
    int a[8] = { 32,16,12,24,36,20,40,28 }; //最大公约数：4
    int L = sizeof(a) / sizeof(int);        //L为元素个数

    int m = a[0];   //初始化最大公约数：a[0]
    for (int i = 1; i < L; i++) //从a[1]开始
    {       
        m = gcd(m, a[i]);
    }

    cout << m;  //输出最大公约数：4

    return 0;
}

上面这种算法很直观，但是会不断调用内部有多次循环的 gcd 算法，在计算大数时较为复杂。因此推荐下面这种优化算法：

（1）对这一组数从大到小进行排序

（2）对每两个相邻的两个数进行如下操作： 　设相邻的两个数为A和B（A在前，因为已经排序，所以A>B），如果A=n*B（n为整数）,也就是A能够被B整除，那么就令A=B；如果A不能被B整除则令A=A%B。

（3）重复（1）、（2）直到数组中每个数都相等，则最大公约数就为这个数。

#include <algorithm>    //想要使用sort函数对数组排序少不了这个头文件
#include <iostream>
using namespace std;

bool cmp(int a, int b)  //cmp函数，确定sort函数排序的规则
{    
    return a > b;
}

int gcd(int num[], int n)   //求多个数的最大公约数的算法
{
    sort(num, num + n, cmp);
    while (num[0] != num[n - 1])
    {
        for (int i = 0; i < n - 1; i++)
        {
            if (num[i] % num[i + 1] == 0)
                num[i] = num[i + 1];
            else
                num[i] = num[i] % num[i + 1];
        }
        sort(num, num + n, cmp);
    }
    return num[0];
}

int main()
{
    int a[8] = { 32,16,12,24,36,20,40,28 }; //最大公约数：4
    int L = sizeof(a) / sizeof(int);        //L为元素个数
    cout << gcd(a, L);                      //输出最大公约数：4

    return 0;
}