LCM of given array elements - GeeksforGeeks

LCM of given array elements - GeeksforGeeks
Given an array of n numbers, find LCM of it.

We know,

The above relation only holds for two numbers,

The idea here is to extend our relation for more than 2 numbers. Let’s say we have an array arr[] that contains n elements whose LCM needed to be calculated.

The main steps of our algorithm are:

1. Initialize ans = arr[0].
2. Iterate over all the elements of the array i.e. from i = 1 to i = n-1
   At the ith iteration ans = LCM(arr[0], arr[1], …….., arr[i-1]). This can be done easily as LCM(arr[0], arr[1], …., arr[i]) = LCM(ans, arr[i]). Thus at i’th iteration we just have to do ans = LCM(ans, arr[i]) = ans x arr[i] / gcd(ans, arr[i])

int gcd(int a, int b)

{

    if (b==0)

        return a;

    gcd(b, a%b);

}

// Returns LCM of array elements

ll findlcm(int arr[], int n)

{

    // Initialize result

    ll ans = arr[0];

    // ans contains LCM of arr[0],..arr[i]

    // after i'th iteration,

    for (int i=1; i<n; i++)

        ans = ( ((arr[i]*ans)) /

                (gcd(arr[i], ans)) );

    return ans;

}

http://www.geeksforgeeks.org/finding-lcm-two-array-numbers-without-using-gcd/

1. Initialize result = 1
2. Find a common factors of two or more array elements.
3. Multiply the result by common factor and divide all the array elements by this common factor.
4. Repeat steps 2 and 3 while there is a common factor of two or more elements.
5. Multiply the result by reduced (or divided) array elements.

unsigned long long int LCM(int arr[], int n)

{

    // Find the maximum value in arr[]

    int max_num = 0;

    for (int i=0; i<n; i++)

        if (max_num < arr[i])

            max_num = arr[i];

 

    // Initialize result

    unsigned long long int res = 1;

 

    // Find all factors that are present in

    // two or more array elements.

    int x = 2;  // Current factor.

    while (x <= max_num)

    {

        // To store indexes of all array

        // elements that are divisible by x.

        vector<int> indexes;

        for (int j=0; j<n; j++)

            if (arr[j]%x == 0)

                indexes.push_back(j);

 

        // If there are 2 or more array elements

        // that are divisible by x.

        if (indexes.size() >= 2)

        {

            // Reduce all array elements divisible

            // by x.

            for (int j=0; j<indexes.size(); j++)

                arr[indexes[j]] = arr[indexes[j]]/x;

 

            res = res * x;

        }

        else

            x++;

    }

 

    // Then multiply all reduced array elements

    for (int i=0; i<n; i++)

        res = res*arr[i];

 

    return res;

}

Read full article from LCM of given array elements - GeeksforGeeks