查找两个数字的LCM

在数学中，最小公倍数(LCM)是可能的最小整数，可以被两个数整除。

LCM可以通过许多方法来计算，例如因式分解等。但是在此算法中，我们将较大的数字乘以1，2，3…。直到找到一个可被第二个数字整除的数字。

输入输出

Input:
Two numbers: 6 and 9
Output:
The LCM is: 18

算法

LCMofTwo(a, b)

输入：两个数字a和b，视为a> b。

输出：  a和b的LCM。

Begin
   lcm := a
   i := 2
   while lcm mod b ≠ 0, do
      lcm := a * i
      i := i + 1
   done

   return lcm
End

示例

#include<iostream>
using namespace std;

int findLCM(int a, int b) {    //assume a is greater than b
   int lcm = a, i = 2;

   while(lcm % b != 0) {    //try to find number which is multiple of b
      lcm = a*i;
      i++;
   }
   return lcm;    //the lcm of a and b
}

int lcmOfTwo(int a, int b) {
   int lcm;
   if(a>b)    //to send as first argument is greater than second
      lcm = findLCM(a,b);
   else
      lcm = findLCM(b,a);
   return lcm;
}

int main() {
   int a, b;
   cout << "Enter Two numbers to find LCM: "; cin >> a >> b;
   cout << "The LCM is: " << lcmOfTwo(a,b);
}

输出结果

Enter Two numbers to find LCM: 6 9
The LCM is: 18