Gcd on three numbers

This is a discussion on Gcd on three numbers within the C Programming forums, part of the General Programming Boards category; Hi there, Recently I got a book on "Algorithms in C". It covers a lot of algorithms and implements them ...

  1. #1
    C / C++
    Join Date
    Jan 2006
    Location
    The Netherlands
    Posts
    312

    Gcd on three numbers

    Hi there,

    Recently I got a book on "Algorithms in C". It covers a lot of algorithms and implements them in C examples.

    There are some exercises in it. One of them is to calculate the gcd (Greatest Common Divisor, Euclid) of three numbers. I have the implementation of two numbers, that's easy.

    I was thinking how to do it. Is it the best way to calculate the gcd of all combinations and then take the lowest of those as the gcd of all three? Or can this be done more efficiently?

    Example:

    Code:
    a = 12
    b = 28
    c = 18
    
    GCD
    a,b: 4
    b,c: 2
    a,c: 6
    
    So the gcd of a,b,c is 2
    Thanks
    Operating Systems:
    - Ubuntu 9.04
    - XP

    Compiler: gcc

  2. #2
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Is it the best way to calculate the gcd of all combinations and then take the lowest of those as the gcd of all three?
    The smallest number is not necessarily the gcd of all three. Consider the set 6, 10, 15:

    gcd(6,10) = 2
    gcd(10,15) = 5
    gcd(6,15) = 3

    But 2 is not a divisor of 15.

    Can you come up with a better approach yourself? ;-)

    Greets,
    Philip
    Last edited by Snafuist; 03-19-2009 at 12:38 PM.
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  3. #3
    C / C++
    Join Date
    Jan 2006
    Location
    The Netherlands
    Posts
    312
    Well, it can be done in a for loop, checking for every number from 1 to 0.5*smallest_number if it's a gcd of all three. Especially with large numbers involved, this would be highly inefficient.

    But I was looking for a solution using the Euclid method, but i'll keep thinking. No hints?
    Operating Systems:
    - Ubuntu 9.04
    - XP

    Compiler: gcc

  4. #4
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    No hints?
    Three numbers may be coprime (i.e. share no common divisor), even if every subset has a divisor greater than 1.

    If I had to compute the greatest common divisor of a set of numbers, I'd compute all prime factors and compute the intersection. The product of all prime factors in the intersection is the gcd of the set.

    Maybe there's a faster method. I'm thinking in mathematical terms here.

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,307
    gcd(a, b, c) == gcd(gcd(a, b), c)
    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"

  6. #6
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    gcd(a, b, c) == gcd(gcd(a, b), c)
    Oops... that's right. Too much work today...

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

  7. #7
    C / C++
    Join Date
    Jan 2006
    Location
    The Netherlands
    Posts
    312
    Hmm, that's the trick. Nope, I wouldn't have thought of that myself!
    Thanks!

    By the way, Snafuist, I don't get your "prime intersection method". The common primes of 6, 10 and 15 are 2, 3 and 5. So 2, 3, and 5 are the intersection?
    Operating Systems:
    - Ubuntu 9.04
    - XP

    Compiler: gcc

  8. #8
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Quote Originally Posted by Ideswa View Post
    By the way, Snafuist, I don't get your "prime intersection method". The common primes of 6, 10 and 15 are 2, 3 and 5. So 2, 3, and 5 are the intersection?
    No. Have a look at the prime factors:
    Code:
    6 --> {2, 3}
    10 --> {2, 5}
    15 --> {3, 5}
    The intersection of these three sets is the empty set, hence the gcd is 1.

    For a non-empty intersection, the gcd is the product of all elements in the intersection. Note that you need multisets in order to preserve the multiplicity of the prime factors.

    Greets,
    Philip
    All things begin as source code.
    Source code begins with an empty file.
    -- Tao Te Chip

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with Rational Numbers (C++)
    By cloudjc in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2008, 04:03 PM
  2. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  3. the definition of a mathematical "average" or "mean"
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 12-03-2002, 10:15 AM
  4. GCD For all of You!
    By Argentina in forum C Programming
    Replies: 0
    Last Post: 02-14-2002, 03:38 PM
  5. A (complex) question on numbers
    By Unregistered in forum C++ Programming
    Replies: 8
    Last Post: 02-03-2002, 05:38 PM

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