Threaded Mode | Linear Mode

***drdebcol*** · (This post was last modified: 01-13-2010 07:23 AM by drdebcol.)

I have explained what is Greatest Common Divisor (GCD) before.
You have Euclidean algorithm for GCD used in this two tasks :
http://www.pro9ramming.com/the-biggest-gcd-t-596.html
http://www.pro9ramming.com/euclid-problem-t-189.html
And you have Binary algorithm for GCD here :
http://www.pro9ramming.com/binary-gcd-al...t-916.html
Lowest Common Multiple and Greatest Common Divisor (GCD) are two important number properties, and they are interrelated. Even though GCD is more often used than LCM, it is useful to learn LCM too.
You can express LCM over GCD like this :

Code:

LCM(m,n)=(m*n)/GCD(m,n)

Here are few examples :

Code:

LCM(6,4)=12

LCM(5,9)=45

LCM(1,2)=2

LCM(7,6)=42

So here is the function for LCM in Pascal :

Code:

function gcd(m,n:longint):longint;

begin

  if n = 0  then

   gcd:=m

  else

   gcd:=gcd(n, m mod n);

end;

function lcm(m,n:longint):longint;

begin

 lcm:=(m*n) div gcd(m,n);

end;

And in C++ :

Code:

int gcd(int a, int b)

{

 if (a == 0)

   return b;

 while (!b == 0)

   if (a > b)

     a=a-b;

   else

     b=b-a;

 return a;

}

int lcm(int a, int b)

{

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

}

FreckleS · 01-13-2010, 07:40 AM

very nice.

***drdebcol*** · 01-14-2010, 05:44 AM

(01-13-2010 07:40 AM)FreckleS Wrote: very nice.

THX I appreciate . . .

Alphablend · (This post was last modified: 01-14-2010 06:06 AM by Alphablend.)

yeah,nice code. Cool