Search code examples
c++lcm

Least common multiple for more than two numbers

I want to find out Least Common Multiple(LCM) of more than two numbers. I know the formula of lcm(a,b) = (a * b) / gcd(a,b). Let's say, I have an array of numbers: [2, 6, 8, 13] and the the lcm should be modulo M = 1000000007.

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?

Solution

  • Knowing that gcd(a, b) represents the product of all the prime factors shared by a and b, what is the significance of a / gcd(a,b)?

    a / gcd(a, b) is equal to the prime factors of a that are not in b.

    Therefore, when you multiple that quantity by b, you get a product of all the prime factors of b and all the prime factors of a that are not in b. This is precisely lcm(a, b).

    Let's extend that to an arbitrary number of integers.

    The lcm(a, b) is a times all the prime factors of b not in a or:

    a * (b / gcd(a, b)) = (a * b) / gcd(a, b)

    Easy enough, you knew that already.

    But if we have a third number, lcm(a, b, c) is a times all the prime factors of b not in a times all the prime factors of c in neither a nor b. Well, the first part is straight forward, it's the same as above:

    lcm(a, b, c) = lcm(a, b) * (all the prime factors of c in neither a nor b)

    How to calculate all the prime factors of c in neither a nor b might not be obvious at first, but it's not overly complicated:

    all the prime factors of c in neither a nor b = c / (gcd(a, c) * gcd(b, c))

    Which means that

    lcm(a, b, c) = lcm(a, b) * c / (gcd(a, c) * gcd(b, c))
lcm(a, b, c) = (a * b * c) / (gcd(a, b) * gcd(a, c) * gcd(b, c))

    And now, you can generalize easily:

    lcm(a[0..N]) = prod(a[0..N]) / pairwise_gcd(a[0..N])

    where pairwise_gcd represents the product of the gcds of the unique pairs from a[0..N]:

    pairwise_gcd(a[0..N]) := gcd_reduce(a[0], {a[1..N]}) * ... * gcd_reduce(a[N-1], {a[N]})
gcd_reduce(x, {y[0..N]}) := gcd(x, y[0]) * ... * gcd(x, y[N])

    With this we can write a recursive version:

    lcm(a[0..N]) = lcm(a[0..N-1]) * a[N] / gcd_reduce(a[N], {a[0..N-1]})

    Which we could have just as easily written the other way:

    lcm(a[0..N]) = a[0] * lcm(a[1..N]) / gcd_reduce(a[0], {a[1..N]})

    giving us that:

    lcm(a[0..N]) = a[0] * prod(a[1..N]) / gcd_reduce(a[0], {a[1..N]}) * pairwise_gcd(a[1..N])
lcm(a[0..N]) = a[0] * prod(a[1] / gcd(a[0], a[1]), ..., a[N] / gcd(a[0], a[N])) / pairwise_gcd(a[1..N])

    Or:

    lcm(a[0..N]) = a[0] * lcm(a[1] / gcd(a[0], a[1]), ..., a[N] / gcd(a[0], a[N]))

    This formulation lends itself to iterative calculation wonderfully.

    Here's an attempt at translating your code snippet to psuedocode

    Compare this to the last definition of lcm on an array, I tried to make them appear similar.

    given int array = arrayOfNums
int product := 1
for numberItem in arrayOfNums
    remove all prime factors of numberItem from all subsequent array elements
    product = product * numberItem
product is now the lcm of arrayOfNums

    And for a sketch of remove all prime factors of x from all subsequent array elements:

    given int array = arrayOfNums
given some element of arrayOfNums = x 
int array restNums := elements of arrayOfNums after x
for otherNum in restNums
    int calcValue := otherNum / gcd(x, otherNum)
    replace otherNum in restNums with calcValue

    Hopefully, that wasn't too confusing; I admit it may not be much of an explanation, but it is a starting point. Please let me know if anything is still unclear.