1. ## GCD

Does anybody have an idea how i can find the greatest common denominator of two numbers in c.

2. How would you do it on paper?

3. Are you referring to the greatest common multiple, or the least common denominator? The greatest common denominator is otherwise infinite. If it's the least common denominator that you're after, I know of a very useful shortcut. I've explained it in section 2 here (particularly sections 2.2 and 2.4). It's just coding it that remains. If it's the greatest common multiple, you'll need to get a list of all prime factors (like the last part of a factor tree) then multiply what each has. 7680x144000 is a recent case of this. 7680 has nine 2's, a 3, and a 5. 144000 has seven 2's, two 3's, and three 5's. Each has seven 2's in common along with a single 3 and a single 5. Multiply the seven 2's with the 3 and the 5 and you get 1920. Apply the same technique when coding it.

4. ## sorry i meant divisor

sorry i meant divisor

but thanks anyhow its good to know

5. Computing the GCD that way is not only horribly inefficient, but much harder to code than using the Euclidean algorithm.

http://en.wikipedia.org/wiki/Euclidean_algorithm

Also, for any m and n, m*n == LCM(m, n)*GCD(m, n), so LCM(m, n) == m*n/GCD(m, n) gives you LCM(m, n) after using the Euclidean algorithm to compute GCD(m, n).

6. Originally Posted by confused87
Does anybody have an idea how i can find the greatest common denominator of two numbers in c.
Seriously, STFW!

If ever there were a problem easy to find the solution to by using a search engine, this would be it!