Q: Given two numbers m and n, write a method to return the first number r that is

divisible by both (e.g., the least common multiple).

A:

The Approach:

What does it mean for r to be divisible by m and n? It means that all the primes in m must go into r, and all primes in n must be in r. What if m and n have primes in common?

For example, if m is divisible by 3^5 and n is divisible by 3^7, what does this mean about r? It means r must be divisible by 3^7.

The Rule: For each prime p such that p^a \ m (e.g., m is divisible by p^a) and p^b \ n, r must be divisible by p^max(a, b)

The Algorithm:

Define q to be 1.

for each prime number p less than m and n:

find the largest a and b such that p^a \ m and p^b \ n

let q = q * p^max(a, b)

return q

## Friday, September 30, 2011

Subscribe to:
Post Comments (Atom)

such an idiotic approach, clearly this guy has no idea about math, check what is the better way to find GCD and then u'll get LCM directly

ReplyDeleteLCM = (m*n)/gcd(m,n)

ReplyDeleteFind gcd(m,n) in log(n) time by Euclid's Method.

Thanks for the approach ... It works

ReplyDeleteThis is a terrible idea, it would require a list of primes. LCM(a,b) = (a*b) / GCD(a,b) .

ReplyDeleteThis would require a list of primes. Better to use LCM(a,b) = (a*b) / GCD(a,b)

ReplyDeleteApproach is correct.

ReplyDeletebest way to get gcd is euclidean formula..assuming m>n gcd(m,n){

ReplyDeleteif n==0 return m;

return gcd(n,m%n);}

nw gcd*lcm=m*n

It's a very complex approach for this kind of problem. Keep it simple :).

ReplyDeleteGiven n and m, what is their LCM ?

- Iterate over each number between n and n*m with a step of n (every multiple of a)

- If the current number x is a multiple of b, then stop, you found it ! (It is the first multiple of b that is also a multiple of a)

Regards.

There's a much much much simpler approach using basic a really basic algorithm:

ReplyDelete- Foreach x between m and m*n with step n

--- If x modulo n == 0

----- break; //x is the least common multiple

I've been studying your algorithm for 20 minutes and its just too confusing. I don't think it would be easy to come up with code that "find[s] the largest a and b such that p^a \ m and p^b \n", I'm also not convinced that that's what you're looking for. I'm pretty sure that algorithm doesn't work in any case, please provide an example with a trace if it does work.

ReplyDeleteI propose a different (read: simpler) algorithm:

public int LCM(int m, int n){

if(m>n){ //ensure n>m

int t = m;

m = n;

n = t;

}

int x = n;

while(x%m != 0) //loop ends when x divided by m gives 0 as the remainder

x+=n;

return x;

}

The idea is to go through multiples of one number until you find one that is divisible by the other number. Sorting the given numbers first ensures that the algorithm only goes through the loop the fewest number of times necessary to produce the correct answer.

#include

ReplyDeletemain(){

int a,b,min,gcd,i,lcm;

scanf("%d%d",&a,&b);

min=a>b?b:a;

for(i=min;i>=1;i--)

if(a%i==0 && b%i==0) break;

gcd=i;

printf("gcd %d",gcd);

lcm=(a/gcd)*(b/gcd);

printf("lcm,, %d",lcm);

return 0;

}

@Original poster - Uh... check for invalid inputs, and then return n*m - prime numbers have nothing to do with the proper solution. You have either posed an incomplete question, answered something completely different, or have no idea what you're doing.

ReplyDeleteIt's look like GCD(http://en.wikipedia.org/wiki/Greatest_common_divisor) mathematics classic problem :

ReplyDelete/**

* Owner : Ghodrat Naderi

* E-Mail: Naderi.ghodrat@gmail.com

* Date : 7/19/12

* Time : 10:25 PM

* IDE : IntelliJ IDEA 11

*/

public class Gcd

{

public static void main(String[] args)

{

int a = 180;

int b = 48;

System.out.println("GCD(" + a + "," + b + ")=" + gcd(a, b));

}

private static int gcd(int a, int b)

{

if (a == 0)

return b;

if (b == 0)

return a;

if (a == b)

return a;

if (a > b)

return gcd(b, a % b);

else

return gcd(a, b % a);

}

}

hi...this is very great post..we can improve our skills from this post..thanks..job interview tips

ReplyDelete