Tìm LCM của hai số

Trong toán học Bội số chung ít nhất (LCM) là số nguyên nhỏ nhất có thể có, chia hết cho cả hai số.

LCM có thể được tính bằng nhiều phương pháp, như thừa số hóa, v.v. nhưng trong thuật toán này, chúng ta đã nhân số lớn hơn với 1, 2, 3…. n cho đến khi chúng ta tìm thấy một số chia hết cho số thứ hai.

Đầu vào và Đầu ra

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

Thuật toán

LCMofTwo(a, b)

Đầu vào: Hai số a và b được coi là a> b.

Đầu ra: LCM của a và b.

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

   return lcm
End

Ví dụ

#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);
}

Đầu ra

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