2つの数値のLCMを見つける

数学では、最小公倍数（LCM）は可能な限り最小の整数であり、両方の数値で割り切れます。

LCMは、因数分解などの多くの方法で計算できますが、このアルゴリズムでは、大きい方の数値に1、2、3…を掛けています。 n2番目の数で割り切れる数が見つかるまで。

入力と出力

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

アルゴリズム

LCMofTwo(a, b)

入力： 2つの数字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