Off-Topic: Re: how to find GCD and LCM in C ?

[Rogério Brito <rbrito@ime.usp.br>]

Hi, Jabka.

On Dec 02 2006, Jabka Atu wrote:
> im studieng math now and many time i need to find GCD (Great Common
> Divider) and LCM (Least Common Member).

I supose that you're talking about integers here, since you didn't say
anything about polynomials, Euclidean Domains and such (and, come to
think of it, if you actually knew about them, you'd know how to compute
that in no amount of time).

Anyway, since this sounds like homework, I will only give you guidelines
for your task:

* first of all, you can find the gdc of two integers a, b (not both
  zero) quite efficiently with Euclid's Algorithm (search the web for
  this). Even more instructive is the use of Euclid's Extented
  Algorithm, which calculates the gdc(a,b) as an (integer) linear
  combination of both a and b;

* second, given the fact that the bot a and b are divisible by gcd(a, b)
  *AND* ab = gcd(a,b) lcm(a,b), you can find the lcm(a,b) quite easily.


Hope this helps, Rogério Brito.

-- 
Rogério Brito : rbrito@ime.usp.br : http://www.ime.usp.br/~rbrito
Homepage of the algorithms package : http://algorithms.berlios.de
Homepage on freshmeat:  http://freshmeat.net/projects/algorithms/