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

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/

**Reply to:**