Please tell the solution of this problem in C language…
Write a C program that calculates the least common multiple (LCM) of ‘n’ numbers.
Input Format:
First line contains the number of numbers that are input ‘n’, where n>1
Second line contains ‘n’ positive integers whose LCM is to be calculated
Output Format:
One line containing the LCM of the ‘n’ numbers
Find the prime factors of each number and their powers. The LCM of all numbers will have a factorisation with the powers of each prime factor being the maximum of that of all the numbers.
Consider the list of numbers,
a[]={12, 16, 60, 35};
12=2^2 * 3^1, so the factor array would be {2,1,0,0,…}
where the ith element denotes the power of the ith prime.
Similarly the factor arrays of all other numbers can be found,
16={4,0,0,0,…}
60={2,1,1,0,…}
35={0,0,1,1,…}
The factor array of the LCM of all numbers would have the ith element equal to the maximum of all the numbers’s ith elements in their factor arrays.
So the LCM would be {4,1,1,1,…}=2^4 * 3^1 * 5^1 * 7^1=1680
Same can be applied to n numbers. You can use lcm(a, b) = a * b/gcd(a,b)
Also this formula only works for two numbers lcm(a, b, c) =/= a * b * c/gcd(a, b, c).
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a%b);
}
int lcm(int[] a, int n) {
int res = 1, i;
for (i = 0; i < n; i++) {
res = res*a[i]/gcd(res, a[i]);
}
return res;
}
@Shubham.Singhal no1 is going to spoon-feed you…please do your own homework…or maybe show what effort you have put in…give us a code that u may have written and we would be happy to help!!!
I concentrated on large number of numbers and larger values(maybe the first 30-40 primes…if not too large…:P) which may lead the numerator to overflow…
this is my code #include <stdio.h> #include <math.h>
int main()
{
int n,i,arr[1000],a=1,j;
scanf("%d\n",&n);
for(i=0;i<=n-1;i++)
{
scanf("%d",&arr[i]);
a=a*arr[i];
}