C++에서 GCD를 사용하지 않고 둘 이상의(또는 배열) 숫자의 LCM 찾기

배열 A가 있고 GCD 연산을 사용하지 않고 모든 요소의 LCM을 찾아야 합니다. 배열이 {4, 6, 12, 24, 30}과 같으면 LCM은 120이 됩니다.

LCM은 두 숫자에 대해 쉽게 계산할 수 있습니다. 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

이 함수를 사용하여 배열의 처음 두 숫자의 LCM을 얻은 다음 LCM의 결과를 사용하여 다음 요소의 LCM을 찾으므로 결과를 얻을 수 있습니다.

예

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

출력

LCM of array elements: 120