LCM stands for Least Common Multiple. Here the program is written to find the LCM of ‘n’ numbers. The value of ‘n’ and ‘n’ numbers is taken as input from the user. For example, if the number of elements be 3, and the given numbers are 12, 15, 18, then we have to find the LCM of 12,15 and 18. Here, first the GCD of each pairs are calculated and we know that,
GCD×LCM=Product of two numbers.
Therefore, LCM= Product of two numbers/GCD.
For the above example, first pair of number is 12, 15.
The GCD of these two numbers: 3.
According to the aforesaid formula:
LCM=
Now, we have to find the LCM of 60 and 18. The GCD of these pair is 6.
Therefore,
LCM=
Therefore, the Least Common Multiple of 12, 15 and 18 is 180.
INPUT: The value of ‘n’ and ‘n’ numbers
OUTPUT: LCM of ‘n’ numbers
PROCESS:
Step 1: [Taking the input]
Read n
For i=0 to n-1 repeat
Read a[i]
[End of ‘for’ loop]
Step 2: [Function to find the ‘GCD’ of two numbers stored in ‘x’ & ‘y’]
While x≠y repeat
If x>y then
Set x<-x-y
Else
Set y<-y-x
[End of ‘if-else’]
[End of ‘while’ loop]
[Returning the gcd]
Return x
[End of the function]
Step 3: [Function to find the ‘LCM’]
Set l<-a[0]
[Finding the lcm]
For i=1 to n-1 repeat
Set l<-(((a[i]×l))/(gcd(a[i],l)))
[End of ‘for’ loop]
Print "The lcm is: l"
[End of function]
Step 4: Stop.
for (i=1;i<n;i++)-------------------------------O(n)
l=(((a[i]*l))/(gcd(a[i],l)));
The time complexity of finding LCM is O(n) where ‘n’ is the number of elements.
The space complexity of this program is O(1) as it requires a constant number of memory spaces for any given input.