Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium


Finding the LCM of given n numbers.

Posted on 2006-03-21
Medium Priority
Last Modified: 2012-06-27
Any one can write the code for finding the LCM of given n numbers.

I have written the code for finding the LCM of 2 numbers, but I need to find the LCM of given n numbers.

int gcd(int a, int b)
      if (a==0 || b==0) return max(a,b);
      if (a > b)       return gcd(b, a);
      if (!(b % a)) return a;
      return gcd(a, b % a);

int lcm(int a, int b)
   return b*a/gcd(a,b);

Question by:picasothakkar
  • 2
LVL 22

Expert Comment

ID: 16252642
Just create a lcm_n function that recursively calls itself or delegates to lcm.

If lcm_n is called with only one number, return that number.
If lcm_n is called with more than one number, then have it call itself recursively.
    a = lcm_n of the first half of the numbers
    b = lcm_n of the second half of the numbers
    return lcm(a,b)
LVL 22

Expert Comment

ID: 16252647
p.s. this sounds suspiciously like homework, thus no code.

Expert Comment

ID: 16253118
wouldn't it be

lcm(a1,...,aN) = lcm(a1,lcm(a2,...aN)) ???

Accepted Solution

DrAske earned 1500 total points
ID: 16254826
I think you can optimize GCDs code to be like:
//assume that a and b cannot both be 0
int GCD(int a, int b)
   if (b==0) return a;
   return GCD(b,a%b);
>>but I need to find the LCM of given n numbers
so, the numbers should be stored in array, right?
then you can do it using for loop :
int array[N];
int output = array[0];    
for(int i = 1; i<N; i++)
     output = lcm(output,array[i]);
or you can do it recursively as  experts said ..

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
Suggested Courses

572 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question