# Greatest Common Divisor.....

• 12-17-2006
muran_pling
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..
• 12-17-2006
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
• 12-17-2006
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.
• 12-17-2006
muran_pling
thanks guys!!! i will try it out :) and let u know how i go
• 12-17-2006
spoon!
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.
• 12-17-2006
muran_pling
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

• 12-17-2006
muran_pling
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 ?
• 12-17-2006
vart
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 ;)
• 12-17-2006
muran_pling
Quote:

Originally Posted by vart
That's what I'm saying ;)

thanks mate! much clearer! :) will try it
• 12-17-2006
muran_pling
ok all done! thanks guys :)
• 12-18-2006
robatino
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.)