Tìm LCM của nhiều hơn hai (hoặc mảng) số mà không sử dụng GCD trong C ++

Chúng ta có một mảng A, chúng ta phải tìm LCM của tất cả các phần tử mà không sử dụng phép toán GCD. Nếu mảng giống như {4, 6, 12, 24, 30} thì LCM sẽ là 120.

LCM có thể được tính toán dễ dàng cho hai con số. Chúng tôi phải làm theo thuật toán này để có được LCM.

getLCM (a, b) -

begin
   if a > b, then m := a, otherwise m := b
      while true do
         if m is divisible by both a and b, then return m
            m := m + 1
   done
end

Sử dụng hàm này để lấy LCM của hai số đầu tiên của mảng, sau đó kết quả của LCM sẽ được sử dụng để tìm LCM của phần tử tiếp theo, do đó chúng ta có thể nhận được kết quả

Ví dụ

#include <iostream>
using namespace std;
int getLCM(int a, int b){
   int m;
   m = (a > b) ? a : b;
   while(true){
      if(m % a == 0 && m % b == 0)
      return m;
      m++;
   }
}
int getLCMArray(int arr[], int n){
   int lcm = getLCM(arr[0], arr[1]);
   for(int i = 2; i < n; i++){
      lcm = getLCM(lcm, arr[i]);
   }
   return lcm;
}
int main() {
   int arr[] = {4, 6, 12, 24, 30};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "LCM of array elements: " << getLCMArray(arr, n);
}

Đầu ra

LCM of array elements: 120