C++求最大公约数算法实现

一、什么是最大公约数

在数学中，最大公约数，简称为gcd，又称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。

例如，12和16的最大公约数是4，一般表示为gcd(12, 16) = 4。

二、求最大公约数的几种方法

目前求最大公约数的方法主要有以下几种：

欧几里得算法

欧几里得算法，又称辗转相除法，是一种简单却又非常高效的求最大公约数的算法。

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

该算法的原理是，设a、b为两个正整数，a>b，令r=a%b，将a替换为b，b替换为r，再计算a%b，直到r=0，则最大公约数为b。

更相减损术

更相减损术是另一种求最大公约数的算法，其原理是，设a、b为两个正整数，a>b，则a-b得到的差值可能是a的约数，也可能是b的约数。如果它是a、b的公约数，那么直接返回这个差值即可；否则，将a、b的较小者替换为a-b，较大者替换为它们的差，继续重复操作直到a或b为0。

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

质因数分解法

质因数分解法是另一种求最大公约数的方法。首先，将两个数分别分解成质因数的乘积；然后，找出它们的所有公共质因数，将这些质因数相乘即为它们的最大公约数。

int gcd(int a, int b) {
    int r = 1;
    for (int i = 2; i > b;
    cout