Greatest Common Divisor.....

This is a discussion on Greatest Common Divisor..... within the C++ Programming forums, part of the General Programming Boards category; Hi guys, just wondering.. how would i work out how to get the greatest common devisor of THREE numbers...not two..but ...

  1. #1
    Registered User
    Join Date
    Aug 2006
    Posts
    33

    Greatest Common Divisor.....

    Hi guys, just wondering.. how would i work out how to get the greatest common devisor of THREE numbers...not two..but THREE numbers.

    for example...

    the greatest common devisors for number 29 are "1 and 29".
    the greatest common devisors for number 6 are "1, 2 and 6".
    the greatest common devisors for number 1981 are "1, 7, 283 and 1981".

    so therefor, the greatest common devisor for these 3 numbers is 1.!!

    i know how to get the greatest common devisor for 2 numbers, but not 3!

    thanks for the help! much appreciated..

  2. #2
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    get for 2
    then take a result as first argument and the third number as a second...
    The GCD for them will be what you're looking for
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  3. #3
    Registered User
    Join Date
    May 2006
    Posts
    903
    Simple. Find all the factors of each of the three numbers and store them in either an array or a vector (I would opt for a vector) and then check if all of them have a common factor. If they do have a common factor, check if there is a greater common factor.

  4. #4
    Registered User
    Join Date
    Aug 2006
    Posts
    33
    thanks guys!!! i will try it out and let u know how i go

  5. #5
    Registered User
    Join Date
    Dec 2006
    Posts
    30
    Quote Originally Posted by Desolation
    Simple. Find all the factors of each of the three numbers and store them in either an array or a vector (I would opt for a vector) and then check if all of them have a common factor. If they do have a common factor, check if there is a greater common factor.
    This is extremely inefficient though.

  6. #6
    Registered User
    Join Date
    Aug 2006
    Posts
    33
    Quote Originally Posted by vart
    get for 2
    then take a result as first argument and the third number as a second...
    The GCD for them will be what you're looking for
    this sounds about right!

  7. #7
    Registered User
    Join Date
    Aug 2006
    Posts
    33
    Quote Originally Posted by vart
    get for 2
    then take a result as first argument and the third number as a second...
    The GCD for them will be what you're looking for
    wait so are you saying.. find out what for example... theres 29, 6 and 1981..
    get the gcd for 29 and 6... which will equal 1...

    then get the gcd for 1 and 1981 ?

  8. #8
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    Quote Originally Posted by muran_pling
    wait so are you saying.. find out what for example... theres 29, 6 and 1981..
    get the gcd for 29 and 6... which will equal 1...

    then get the gcd for 1 and 1981 ?
    That's what I'm saying
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  9. #9
    Registered User
    Join Date
    Aug 2006
    Posts
    33
    Quote Originally Posted by vart
    That's what I'm saying
    thanks mate! much clearer! will try it

  10. #10
    Registered User
    Join Date
    Aug 2006
    Posts
    33
    ok all done! thanks guys

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    And of course you can generalize to finding the GCD of n_1, ..., n_i. Find the GCD of n_1 and n_2, take the GCD of that with n_3, take the GCD of that with n_4, etc. If you want, you can stop when one of the results is 1, since the GCD of 1 with anything is 1. (Just to check - you're using Euclid's Algorithm to compute the GCD, right? It's much more efficient than factoring.)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Greatest Common Factor
    By cppdungeon in forum C++ Programming
    Replies: 5
    Last Post: 11-28-2005, 11:06 AM
  2. Greatest Common Divisor problem
    By fenixataris182 in forum C++ Programming
    Replies: 8
    Last Post: 07-12-2005, 08:55 PM
  3. Greatest common divisor
    By wiz23 in forum C++ Programming
    Replies: 5
    Last Post: 04-13-2005, 05:50 PM
  4. Greatest common divisor with int and double
    By wiz23 in forum C++ Programming
    Replies: 3
    Last Post: 04-12-2005, 05:38 PM
  5. Greatest Common Factor problem
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 10-08-2001, 04:29 PM

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