LCM of Two Numbers in C++

Algorithm to Find LCM of Two Numbers

LCM of two integers a and b is the smallest positive integer that is divisible by both a and b.

To calculate the LCM of two numbers in C++, we can simply find the prime factors of both numbers and take the union of these factors. The product of all the numbers in the union will give us the least common factor of the two numbers. For example, take a = 42 and b = 63 as the two numbers.

Prime factors of a: {2, 3, 7}. Prime factors of b: {3, 3, 7}. Union: {2, 3, 3, 7}.

LCM(a , b) = 2*3*3*7= 126.

Another approach can be using the below formula to calculate the LCM of two numbers.

The product of the Least Common Multiple(LCM) and Greatest Common Divisor(GCD) of two numbers a and b is equal to the product of numbers a and b itself.'

Here, the Greatest Common Divisor(GCD), as the name suggests, is nothing but the largest positive integer that divides each of the numbers a and b.

Let's take the above example, a = 42 and b = 63

GCD(a , b)= Product of intersection of all the prime factors of a and b = 3*7= 21.

Program to Find LCM of Two Numbers Using if Statement

We can find the LCM of two numbers a and b by getting the first smallest number which is divisible by both a and b. We can initialize a variable max_num with maximum(a , b) and then increment max_num by 1 till max_num is divisible by both a and b using the if condition.

Output:

Time Complexity:

O(a*b) as the while loop will run till it reaches the least common multiple of a and b. For example, 13 and 7 are the prime numbers whose LCM is 91. Here the loop starts from max(13,7)= 13 and ends at 91. Hence, the time complexity is found to be O(a*b).

Space Complexity:

O(1) extra space is required as we are using int to save the previously calculated result.

Program to Get LCM of Two Numbers using GCD (While Loop)

In Mathematics, we know that The product of the Least Common Multiple(LCM) and Greatest Common Divisor(GCD) of two numbers a and b is equal to the product of the numbers a and b itself.

Deducing the above statement:

We can find the LCM of two numbers, a' and b, by finding GCD(a, b)` using a while loop and then dividing the product of a and b with GCD(a, b). To find the GCD(a , b), we can apply the Euclidean algorithm by subtracting the smaller number from the larger between a and b until both the numbers are equal. The number found after the termination of the while loop is GCD(a , b). For example, let us take a = 14 and b = 35.

Iteration 1: We subtract a from b: a = 14 and b = 35-14= 21.

Iteration 2: We subtract a from b again as a<b: a = 14 and b = 21-14= 7.

Iteration 3: We subtract b from a as a>b: a = 14-7= 7 and b = 7 We got a = b = 7. Therefore, GCD( 14, 35 )= 7

Output:

Time Complexity:

O(max(a , b)): As we know that in each iteration, we are subtracting either a from b or b from a. Hence, we can say max(a , b) iterations will give us the GCD of a and b.

Space Complexity:

O(1) extra space is required as we are using int to save the previously calculated result.

Program to Get the LCM of Two Numbers Using GCD (Recursion)

We can find the LCM of two numbers a and b by using the formula:

We can apply the Euclidean algorithm to find the GCD of a and b by subtracting the smaller number from the larger number between a and b and then recursively passing a and b to the same function.

Output

Time Complexity:

O(max(a , b)): As we know that in each recursive call, we are subtracting either a from b or b from a. Hence, we can say max(a , b) iterations will give us the GCD of a and b.

Space Complexity:

O(max(a , b)) extra space is required as total recursive calls are equal to the number of iterations until we get the GCD of the two numbers a and b.

Program to Get the LCM of Array Elements using Function and While Loop

We know that, LCM(a,b)= a * b / GCD(a,b) is valid for two numbers but for elements more than two we cannot apply the similar formula like

Let’s say we have an array arr[] that contains n elements whose LCM is to be calculated.

We can apply the following algorithm:

For example, let us take an array arr[]= {42, 63, 72, 49}. Iteration 1: We take first two elements: a = 42 and b = 63. LCM(42,63)= 42*63 / GCD(42, 63)= 126. So, answer for the first two elements: ans = 126.

Iteration 2: We take the next element from the array and find the LCM with the previously calculated ans: a = ans = 126 and b = 72. LCM(126,72)= 126*72 / GCD(126, 72)= 504 So, update the ans: ans = 504.

Iteration 3: Similarly, we take the next element and find the LCM with the previously calculated ans: a = ans = 504 and b = 49. LCM(504,49)= 504*49 / GCD(504, 49)= 3528 So, update the ans: ans = 3528. Hence, we get the LCM of the given array as 3528.

Implementation:

Output:

Time Complexity:

O( n * (max(a,b)) ) where n is the size of the given array and a and b are the numbers taken into consideration at every iteration i.e. ans and the next element in the array. For n elements in the array, we are calculating LCM in max(a,b) operations. Hence, time complexity is found to be O( n * (max(a,b)) ).

Space Complexity:

O(max(a,b)) extra space is required as total recursive calls are equal to the number of iterations until we get the GCD of the two numbers a and b.