求两数最大公约数之解法

#include 

using namespace std;


int getCommonNum(int a, int b)
{
    //定义一个c变量存储a除b之后的余数
    int c = a % b;
    //如果余数不为零进入循环
    while (c != 0)
    {
 //让被除数等于除数
 a = b;
 //让除数等于余数
 b = c;
 //让c等于交换后的a除b的余数
 c = a % b;
    }
    //如果能执行到这一步，说明最大公约数已经找到了（至少也是1）
    return b;
}


int getCommonNum2(int a, int b)
{
    //定义m为a和b中较小的那一个
    int m = min(a, b);
    //以m为标准进行循环，从大到小（因为是最大公约数）
    for (int i = m; i >= 1; i--)
    {
 if (a % i == 0 && b % i == 0)
 {
     //如果能满足a，b同时被i整除，那么就直接返回i（因为i一定是最大公约数）
     return i;
 }
    }
}


int getCommonNum3(int a, int b)
{
    //让c等于a，b中较大数除以较小数的余数
    int c = max(a, b) % min(a, b);
    if (c == 0)
    {
 //如果余数为零，则直接返回较小数，因为它是最大公约数
 return min(a, b);
    }
    //否则从较小数的一半开始蛮力测试
    int d = b / 2;
    for (int i = d; i >= 1; i--)
    {
 if (a % i == 0 && b % i == 0)
 {
     //如果能满足a，b同时被i整除，那么就直接返回i（因为i一定是最大公约数）
     return i;
 }
    }
}


int getCommonNum4(int a, int b)
{
    //定义一个存储公约数的数组
    int commonArr[min(a, b)];
    //这是数组当前的元素个数
    int index = 0;
    //这是循环标签
    //这里巧妙地使用goto语句实现了既能直走又能回旋的逻辑
    LOOP:
 //从两者最小的一个开始蛮力测试
 for (int i = 2; i <= min(a, b); i++)
 {
     //如果能满足则找到一个公约数，肯定是最小公约数
     if (a % i == 0 && b % i == 0)
     {
  //加入公约数数组
  commonArr[index++] = i;
  //改变a，b已被公约数除过的值
  a /= i;
  b /= i;
  //回到LOOP标签，继续执行此步奏
  goto LOOP;
     }
 }
 //如果循环能执行到这一步，说明此时的a，b，已经没有最小公约数了
    //将最大公约数定义为1，因为有可能之前定义的公约数数组为空
    int commonNum = 1;
    //遍历公约数数组
    for (int i = 0; i < index; i++)
    {
 //将公约数连乘
 commonNum *= commonArr[i];
    }
    //终于大功告成，返回最大公约数（最起码也是个1）
    return commonNum;
}


int getCommonNum5(int a, int b)
{
    //定义一个存储中间减值得变量
    int l;
    do {
 //无论如何先执行一次
 //大的减小的
 l = max(a, b) - min(a, b);
 a = min(a, b);
 b = l;
    //如果相等，则找到最大公约数
    } while (a != b);
    //返回最大公约数
    return l;
}

int main()
{
    cout << getCommonNum(112, 24) << endl;
    cout << getCommonNum2(112, 24) << endl;
    cout << getCommonNum3(112, 24) << endl;
    cout << getCommonNum4(112, 24) << endl;
    cout << getCommonNum5(112, 24) << endl;
    return 0;
}