GCD

This is a discussion on GCD within the C Programming forums, part of the General Programming Boards category; Does anybody have an idea how i can find the greatest common denominator of two numbers in c....

  1. #1
    Registered User
    Join Date
    May 2007
    Posts
    2

    Red face GCD

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

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    How would you do it on paper?

  3. #3
    Math wizard
    Join Date
    Dec 2006
    Location
    USA
    Posts
    582
    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

  4. #4
    Registered User
    Join Date
    May 2007
    Posts
    2

    sorry i meant divisor

    sorry i meant divisor

    but thanks anyhow its good to know

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Quote Originally Posted by confused87 View Post
    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!
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Gcd on three numbers
    By Ideswa in forum C Programming
    Replies: 7
    Last Post: 03-19-2009, 01:57 PM
  2. NEED help with returning the GCD
    By SuPaNooB in forum C Programming
    Replies: 3
    Last Post: 11-04-2007, 11:16 AM
  3. GCD as fast as possible!
    By fischerandom in forum C Programming
    Replies: 21
    Last Post: 11-22-2005, 10:20 AM
  4. gcd
    By Kayoss in forum C++ Programming
    Replies: 4
    Last Post: 10-12-2005, 01:44 PM
  5. GCD For all of You!
    By Argentina in forum C Programming
    Replies: 0
    Last Post: 02-14-2002, 03:38 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21