求任意两个正整数的最大公约数和最小公倍数

这里用辗转相除法（也叫欧几里德算法）进行分析，辗转相除法是求最大公约数（GCD:Greatest Common Divisor）的算法，其原理是：两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。注意：从其原理的角度出发，可以按下面两种方法计算出最大公约数，然后很容易就得到两个正整数的最小公倍数（LCM:Least Common Multiple）。

一种是递归算法：假设求GCD的函数名为gcd，其中自然要有两个参数（较小的数min和两数的相除余数max%min），即为gcd(min, max%min)，C++实现代码如下：

#include <iostream>

using namespace std;

unsigned int Gcd(unsigned int max, unsigned int min);

int main()
{
    unsigned int num1, num2, max, min, gcd, lcm;
    cout << "Enter two numbers: ";
    cin >> num1 >> num2;

    if(num1 < num2)
    {
            min = num1;
            max = num2;
            }
    max = num1;
    min = num2;

    gcd = Gcd(max, min);
    lcm = num1*num2/gcd;

    cout << "gcd: " << gcd << endl;
    cout << "lcm: " << lcm << endl;

    system("pause");
    return 0;
    }

    unsigned int Gcd(unsigned int max, unsigned int min)
    {
             unsigned int temp;
             if(max%min == 0)
                        return min;
             else
             {
                 temp = min;
                 min = max%min;
                 max = temp;
                 return Gcd(max, min);
                 }
             }

输出结果如下：

另一种方法是利用while循环实现，而其循环条件就是原理中的两数的相除余数，通过判断其是否为0来实现：

#include <iostream>

using namespace std;

int main()
{
    unsigned int num1, num2, temp, max, min, gcd, lcm;
    cout << "Enter two number: ";
    cin >> num1 >> num2;

    if(num1 < num2)
    {
            min = num1;
            max = num2;
            }
    min = num2;
    max = num1;

    while(max%min)
    {
                    temp = min;
                    min = max%min;
                    max = temp;
                    }
    //get the gcd: min
    gcd = min;
    lcm = num1*num2/gcd;

    cout << "gcd: " << gcd << endl;
    cout << "lcm: " << lcm << endl;

    system("pause");
    return 0;
    }

输出结果如下：