C++实现最小公倍数求解不使用数组的方法 |21xrx.com

C++实现最小公倍数求解不使用数组的方法

2023-07-13 12:43:07 深夜i -- --

C++ 最小公倍数不使用数组

最小公倍数，指的是多个数共同的倍数中最小的一个。在数学中，求解最小公倍数是一项基本的计算任务。而在编程中，使用C++编写代码实现最小公倍数的问题也是不可避免的。

通常情况下，我们可以使用数组来存储需要计算最小公倍数的数字，然后再通过循环遍历数组中的元素，找到它们的公倍数。但是，本文将介绍一种不使用数组的方法来实现最小公倍数的求解。

方法一：使用累加思路

解题思路：

1、使用循环依次枚举出两个数字的所有倍数，并取最小公倍数的公共部分；

2、利用辗转相除法求解出两个数的最大公约数；

3、使用两个数的积，除以它们的最大公约数，即可得到它们的最小公倍数。

代码实现：


#include<iostream>
using namespace std;
int gcd(int a,int b)//辗转相除法求解最大公约数
{
  return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b)//求解最小公倍数
{
  if(a<b) swap(a,b);//将较大值放在a上
  for(int i=1;i<=b;i++)
  {
    if((a*i)%b==0) //找到最小公倍数
    {
      return a*i;
      break;
    }
  }
  return a*b/gcd(a,b);//防止无法找到最小公倍数
}
int main()
{
  int a,b;
  cin>>a>>b;
  int ans=lcm(a,b);
  cout<<ans<<endl;
  return 0;
}

方法二：使用数学方法

解题思路：

1、使用两个数的积除以它们的最大公约数，得到它们的最小公倍数。

代码实现：


#include<iostream>
using namespace std;
int gcd(int a,int b)//辗转相除法求解最大公约数
{
  return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b)//求解最小公倍数
{
  return a*b/gcd(a,b);
}
int main()
{
  int a,b;
  cin>>a>>b;
  int ans=lcm(a,b);
  cout<<ans<<endl;
  return 0;
}

总结：

本文介绍了两种求解最小公倍数的方法，一种是使用累加思路，一种是使用数学方法。无论哪种方法，都需要使用最大公约数的知识。在实践中，我们可以根据具体情况选择哪种方法来实现最小公倍数的求解。

上一篇: idea打包java可执行jar包

下一篇: Visual C++6.0无法打开，请问如何解决？

评论区

()

相似文章