在C++中，求公约数和公倍数是常见的数学操作。公约数指的是两个数能够同时整除的最大正数，而公倍数指的是两个数的共同倍数中最小正数。下面我们将分别介绍如何在C++中求出两个数的公约数和公倍数。

求公约数

求公约数有多种方法，比如常见的辗转相除法、欧几里得算法等。下面我们以辗转相除法为例来介绍如何在C++中求两个数的公约数。该方法的实现代码如下：

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

在上述代码中，我们使用递归的方式实现辗转相除法。具体而言，如果b等于0，则a为最大公约数；否则，我们将a和b交换位置，并计算a除以b的余数，然后再以此余数和b作为新的一组数继续递归。这样不断递归下去，直到得到最终的最大公约数。

例如，我们要求出120和48的最大公约数，可以调用上述函数，如下所示：

int result = gcd(120, 48);
cout << result << endl; // 输出12

该函数的时间复杂度为O(log n)，其中n是a和b的较大值。

求公倍数

求公倍数的方法比较简单，只需要利用公式LCM(a,b) = a * b / GCD(a,b)，即最小公倍数等于两数之积除以最大公约数。下面我们来看一下如何在C++中实现这个公式：

int lcm(int a, int b){
  return a * b / gcd(a, b);
}

在上述代码中，我们先调用前面介绍的求公约数函数gcd()，然后根据公式计算出最小公倍数。

例如，我们要求出15和20的最小公倍数，可以调用上述函数，如下所示：

int result = lcm(15, 20);
cout << result << endl; // 输出60

该函数的时间复杂度与求公约数函数相同，也是O(log n)。

结语

在C++中求公约数和公倍数是常见的数学操作，其实现方法也比较简单。大家可以根据上述介绍来实现自己的代码，并且在日常编程中灵活应用。

相似文章

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政