Does anybody have an idea how i can find the greatest common denominator of two numbers in c.
GCD
Does anybody have an idea how i can find the greatest common denominator of two numbers in c.
How would you do it on paper?
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.
Last edited by ulillillia; 05-03-2007 at 08:54 PM. Reason: sections 2.2 AND 2.4, not through
sorry i meant divisor
but thanks anyhow its good to know
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).
Last edited by robatino; 05-03-2007 at 09:04 PM.
Seriously, STFW!Originally Posted by confused87
If ever there were a problem easy to find the solution to by using a search engine, this would be it!
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
