C++ 查找两个数字的最大公约数

在本教程中，我们将写一个C++程序来查找两个数字的最大公约数。

最大公约数（GCD，又称为最大公因数）也称为HCF（最高公共因子）。

例如

36 = 2 * 2 * 3 * 3

60 = 2 * 2 * 3 * 5

这两个数字的最大公因数是2、2和3。

因此，这两个数字的HCF是2 * 2 * 3 = 12

20 = 2 * 2 * 5

28 = 2 * 2 * 7

这两个数字的最大公因数是2和2。

因此，这两个数字的HCF是2 * 2 = 4。

方法1

可以通过找到两个数字的所有质因数，然后找到公共因数并返回它们的乘积来解决该问题。

找到第一个数字的因数
找到第二个数字的因数
找到两个数字的公共因数
将它们相乘得到GCD

C++代码

#include 
#define MAXFACTORS 1024 // Let us consider max factors can be 1024
using namespace std;

typedef struct 
{

    int size;
    int factor[MAXFACTORS + 1];
    int exponent[MAXFACTORS + 1];

} FACTORIZATION;

// Function to find the factorization of M and N
void FindFactorization(int x, FACTORIZATION* factorization)
{
    int i, j = 1;
    int n = x, c = 0;
    int k = 1;
    factorization->factor[0] = 1;
    factorization->exponent[0] = 1;

    for (i = 2; i <= n; i++) {
        c = 0;

        while (n % i == 0) {
            c++;

            // factorization->factor[j]=i;
            n = n / i;
            // j++;
        }

        if (c > 0) {
            factorization->exponent[k] = c;
            factorization->factor[k] = i;
            k++;
        }
    }

    factorization->size = k - 1;
}



// function to find the gcd using Middle School procedure
int gcdMiddleSchoolProcedure(int m, int n)
{

    FACTORIZATION mFactorization, nFactorization;

    int r, mi, ni, i, k, x = 1, j;

    // Step 1.
    FindFactorization(m, &mFactorization);


    // Step 2.
    FindFactorization(n, &nFactorization);


    // Steps 3 and 4.
    // Procedure algorithm for computing the
    // greatest common divisor.
    int min;
    i = 1;
    j = 1;
    while (i <= mFactorization.size && j <= nFactorization.size) {
        if (mFactorization.factor[i] < nFactorization.factor[j])
            i++;

        else if (nFactorization.factor[j] < mFactorization.factor[i])
            j++;

        else /* if arr1[i] == arr2[j] */
        {
            min = mFactorization.exponent[i] > nFactorization.exponent[j]
                    ? nFactorization.exponent[j]
                    : mFactorization.exponent[i];

            x = x * mFactorization.factor[i] * min;
            i++;
            j++;
        }
    }

    return x;
}


int main()

{

    int m = 36, n = 60;
    cout << "GCD of " << m << " and " << n << " is "
        << gcdMiddleSchoolProcedure(m, n);

    return (0);
}

输出

GCD of 36 and 60 is 12

方法2

可以使用欧几里得算法高效地解决方法1。该算法的思想是，如果从较大的数中减去较小的数，最大公约数不会改变。

C++代码

#include <iostream>
using namespace std;

int gcd(int a, int b) // The function runs recursive in nature to return GCD
{

    if (a == 0) // If a becomes zero
       return b; // b is the GCD 
    if (b == 0)// If b becomes zero
       return a;// a is the GCD 


    if (a == b) // The case of equal numbers 
        return a; // return any one of them 

   // Apply case of substraction 
    if (a > b) // if a is greater subtract b 
        return gcd(a-b, b);
    return gcd(a, b-a); //otherwise subtract a 
}


int main()
{
    int a = 36, b = 60;
    cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);
    return 0;
}

输出

GCD of 36 and 60 is 12

方法3

第二种方法可以进一步优化，使用取模运算符而不是减法。

C++代码

#include <iostream>
using namespace std;

int gcd(int a, int b) // The function runs recursive in nature to return GCD
{
    if (b == 0) // if b becomes 0 return a 
        return a;
    return gcd(b, a % b); // divide to a by b to make smaller number 

}


int main()
{
    int a = 60, b = 36;
    cout<<"GCD of "<<a<<" and "<<b<<" is "<<gcd(a, b);
    return 0;
}

输出