How the LCM calculation logic is being done?

programming
Tags: #<Tag:0x00007f242275fbf0>

#1

I have seen below code to calculate the LCM of multiple numbers but I am not understanding how the calculation is going on with both the loops.

int arr[] = {2, 6, 8, 13}, n = 4
long long int ans=1;
long long int M=1000000007;
for(int i=0;i<n;i++)   // Calculating LCM
{
    for(int j=i+1;j<n;j++)
    {
        arr[j]=arr[j]/__gcd(arr[i],arr[j]);
    }
    ans=((ans%M)*(arr[i]%M))%M;
}
return (ans)%M;

Can anyone please help me to understand the LCM calculation in the above code?


#3

There is a property in mathematics which says for two numbers n1 and n2 , gcdlcm == n1n2 . so instead of finding lcm we find gcd and then divide it with the product of numbers.
.