Chương trình C ++ để tìm LCM

Bội số chung ít nhất (LCM) của hai số là số nhỏ nhất là bội số của cả hai.

Ví dụ:Giả sử chúng ta có hai số sau:15 và 9.

15 = 5 * 3
9 = 3 * 3

Vì vậy, LCM của 15 và 9 là 45.

Một chương trình để tìm LCM của hai số được đưa ra như sau -

Ví dụ

#include <iostream>
using namespace std;
int main() {
   int a=7, b=5, lcm;
   if(a>b)
   lcm = a;
   else
   lcm = b;
   while(1) {
      if( lcm%a==0 && lcm%b==0 ) {
         cout<<"The LCM of "<<a<<" and "<<b<<" is "<<lcm;
         break;
      }
      lcm++;
   }
   return 0;
}

Đầu ra

The LCM of 7 and 5 is 35

Trong chương trình trên, biến lcm được đặt là lớn hơn trong hai số. Điều này được chứng minh bằng cách sử dụng đoạn mã sau.

if(a>b)
lcm = a;
else
lcm = b;

Sau đó, một vòng lặp sẽ chạy. Trong vòng lặp này, nếu LCM chia hết cho a và b, nó là LCM của hai số và được hiển thị. Nếu không, LCM sẽ tăng lên cho đến khi điều kiện này được đáp ứng.

Đoạn mã giải thích điều này như sau -

while(1) {
   if( lcm%a==0 && lcm%b==0 ) {
      cout<<"The LCM of "<<a<<" and "<<b<<" is "<<lcm;
      break;
   }
   lcm++;
}

Một phương pháp khác để tìm LCM của hai số là sử dụng công thức LCM và GCD. Công thức này chỉ định rằng tích của hai số bằng tích của LCM và GCD của chúng.

a * b = GCD * LCM

Một chương trình để tìm LCM của hai số bằng công thức được đưa ra như sau -

Ví dụ

#include<iostream>
using namespace std;
int gcd(int a, int b) {
   if (b == 0)
   return a;
   return gcd(b, a % b);
}
int main() {
   int a = 7, b = 5;
   cout<<"LCM of "<< a <<" and "<< b <<" is "<< (a*b)/gcd(a, b);
   return 0;
}

Đầu ra

The LCM of 7 and 5 is 35

Trong chương trình trên, LCM được tìm thấy bằng cách sử dụng công thức. Đầu tiên, GCD của a và b thu được bằng cách sử dụng gcd (). Đó là một hàm đệ quy. Nó có hai tham số, tức là a và b. Nếu b lớn hơn 0, thì a được trả về hàm main (). Nếu không thì hàm gcd () tự gọi đệ quy với các giá trị b và a% b.

Điều này được chứng minh bằng cách sử dụng đoạn mã sau.

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

Sau khi thu được GCD, LCM được tính theo công thức. Sau đó, nó được hiển thị. Điều này được hiển thị trong đoạn mã sau.

cout<<"LCM of "<< a <<" and "<< b <<" is "<< (a*b)/gcd(a, b);