LCM of n numbers

general
,
1

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

2 Likes
2

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

3

Their LCM is a1a2…*an/gcd(a1,a2,…,an), gcd can be calculated with Euclid’s algorithm.

4

Note that lcm(a1, a2, a3) = lcm(lcm(a1, a2), a3)

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;
}
7 Likes
5

u asked how to include all array elements into if stmt. This is how u can do it:

for(i=0;i<n;i++)
if(j%a(i)!=0) break;

if(i==n){printf("%d",j)//lcm
break;//break out of j loop
}

p.s eventhough ur prg will work well its time complexity is more so prefer cOd3junki’s soln in timed contests

1 Like
6

include < stdio.h >

include < math.h >

//gcd method definition
int gcd(int a, int b) {

if (b == 0)

return a;

return gcd(b, a%b);
}

//LCM method definition
int LCM(myarray[n])

int Lcmvalue, z;

for(int z = myarray[0],x=1, i=1, y=2, y< myarray[n].length; myarray[i]+=2, myarray[y]+=2) {

z = gcd( gcd(z,myarray[i]), myarray[y]);

Lcmvalue = (x *= myarray[i])/ z;

return Lcmvalue;

}

//main
int main() {

int n;

Printf("ENTER NUMBER OF DIGITS );

Scanf("%d", n);

If (n>1) {

int myarray[n];

//ENTERING DIGITS INTO ARRAY

Printf(“ENTER THE DIGITS\n”)

for(int i = 0, i< myarray.length, i++) {

Scanf("%d%",myarray[i])

}

LCM(myarray[n]);

return 0;

}

1 Like
7

Finally i made my code…thanks all of u for ur valuable suggestions…
#include <stdio.h>
#include <stdlib.h>

int main()
{
int n,i,arr[5],a=1,j,k;
scanf("%d\n",&n);
for(i=0;i<=n-1;i++)
{
scanf("%d",&arr[i]);
a=a*arr[i];
}

for(j=1;j<=a;j++)
{
    for(k=0;k<=n-1;k++)
    {
      if(j%arr[k]!=0)
      {
        break;
      }
    }
    if(k>n-1)
    break;
}
printf("%d",j);
return 0;

}

8

i want the c code… and the numbers are not given before, they have to be entered by the user…also it depends on user how many no.s he input…

9

@c0d3junki3…there wasn’t anything wrong in this answer…also then u propose a similar(if not exactly the same) solution…so y downvote…!!!

10

@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!!!

11

because it’s incorrect mathematically, the formula that is

it doesn’t work for example for (1, 2, 4)

by his formula lcm(1, 2, 4) = 1 * 2 * 4 / gcd(1, 2, 4) = 1 * 2 * 4 / 1 = 8

a*b/gcd(a, b) works only for two numbers

1 Like
12

my bad…sorry…overlooked that…!!

13

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…:slight_smile:

14

@kunal361 This answer is incorrect. Consider the numbers a1,a2,a3= 2,2,2. Product of a1a2a3=8 and gcd is 2. So lcm comes out to be 4 by this method.

15

@kcahdog thanks…also i had accepted to what @c0d3junki3 had explained…also please do read my comment above…:slight_smile:

16

Yep, my bad indeed, you should go 1 by 1, ignore this comment.

17

@kunal361

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];
}

for(j=1;j<=a;j++)
if(j%arr[0]==0 && j%arr[1]==0 && j%arr[2]=00…)
{
printf("%d",j);
break;
}
return 0;
}

Now my problem is that, how to include all the element of array in If statement…