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

x
?
Solved

Finding the LCM of given n numbers.

Posted on 2006-03-21
4
Medium Priority
?
440 Views
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);
}


0
Comment
Question by:picasothakkar
  • 2
4 Comments
 
LVL 22

Expert Comment

by:NovaDenizen
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)
0
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 16252647
p.s. this sounds suspiciously like homework, thus no code.
0
 
LVL 2

Expert Comment

by:zulti
ID: 16253118
wouldn't it be

lcm(a1,...,aN) = lcm(a1,lcm(a2,...aN)) ???
0
 
LVL 9

Accepted Solution

by:
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 ..
regards;
0

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