C++程序查找两个数字的最大公约数或最小公倍数

两个数字的最大公因数（Greatest Common Divisor，简称GCD）或最小公倍数（Highest Common Factor，简称HCF）是它们都能整除的最大的数字。

例如，20和28的最大公因数是4，98和56的最大公因数是14。 求解方法： 假设a=98，b=56。由于a>b，所以将a=a-b，而b保持不变，于是a=98-56=42，b=56。由于现在b>a，所以将b=b-a，而a保持不变，因此b=56-42=14，a=42。42是14的3倍，因此 HCF 是14。同样，a=36，b=60，在这里b>a，因此b=24，a=36，现在a>b，所以a=12，b=24。12是36和60的HCF。这个方法总是有效的。

一种简单的解法 是查找两个数字的所有质因数，然后找到两个数字中都存在的因数的交集。最后返回交集中元素的乘积。

更有效的解法 是使用欧几里得算法，这是用于此目的的主要算法。这个方法的思想是，如果从一个大数中减去一个小数，则两个数字的GCD不会改变。

// C++ program to find GCD 
// of two numbers
#include <iostream>
using namespace std;

// Recursive function to return 
// gcd of a and b
int gcd(int a, int b)
{
    // Everything divides 0 
    if (a == 0)
       return b;
    if (b == 0)
       return a;

    // base case
    if (a == b)
        return a;

    // a is greater
    if (a > b)
        return gcd(a-b, b);
    return gcd(a, b-a);
}

// Driver code
int main()
{
    int a = 98, b = 56;
    cout << "GCD of " << a << 
            " and " << b << 
            " is " << gcd(a, b);
    return 0;
}

输出：

GCD of 98 and 56 is 14

时间复杂度： O(min(a,b))

辅助空间： O(min(a,b))

动态规划 方法 ( 自上而下带备忘录的方法 ) :

// C++ program to find GCD of two numbers
#include <bits/stdc++.h>
using namespace std;

int static dp[1001][1001];

// Function to return gcd of a and b
int gcd(int a, int b)
{
    // Everything


                    // divides 0
                    if (a == 0)
                        return b;
                    if (b == 0)
                        return a;

                    // base case
                    if (a == b)
                        return a;

                    // if a value is already
                    // present in dp
                    if (dp[a][b] != -1)
                        return dp[a][b];

                    // a is greater
                    if (a > b)
                        dp[a][b] = gcd(a - b, b);

                    // b is greater
                    else
                        dp[a][b] = gcd(a, b - a);

                    // return dp
                    return dp[a][b];
                }

                // Driver code
                int main()
                {
                    int a = 98, b = 56;
                    memset(dp, -1, sizeof(dp));
                    cout << "GCD of " << a <<
                        " and " << b <<
                        " is " << gcd(a, b);
                    return 0;
                }

输出

GCD of 98 and 56 is 14

时间复杂度： O(min(a,b))

辅助空间： O(1)

更 有效的解法 是在欧几里得算法中使用模运算。

// C++程序查找两个数的最大公约数
# include <iostream>
using namespace std;
  
// 递归函数在一行返回a和b的gcd
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);    
}
   
// 主函数
int main()
{
    int a = 98, b = 56;
    cout << "GCD of " << a << 
            " and " << b << 
            " is " << gcd(a, b);
    return 0;
}

输出:

GCD of 98 and 56 is 14

时间复杂度: O(log(min(a,b))

辅助空间: O(log(min(a,b))

上述算法的时间复杂度是O(log(min(a,b)))，这是从最坏情况的分析中得出的。我们询问哪两个最小的数字需要1步，它们将是（1,1）。如果我们想将步数增加到2，同时尽可能少，我们可以将数字设置为（1,2）。同样，对于3步，数字将是（2,3），4将是（3,5），5将是（5,8）。因此，我们可以注意到这里有一个模式，对于第n步，数字将是（fib（n），fib（n + 1））。因此，最坏情况下的时间复杂度将是O（n），其中a>= fib（n）和b>= fib（n + 1）。

现在，斐波那契数列是一个呈指数增长的数列，其中第n /（n-1）个项的比率趋近于（sqrt（5）+1）/2，也称为黄金比率。因此，我们可以看到，随着期限呈指数增长，算法的时间复杂度以线性方式增加，因此时间复杂度将是log（min（a,b））。