Thread: 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..

thanks guys!!! i will try it out and let u know how i go

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.

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!

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 ?

Originally Posted by vart

That's what I'm saying

thanks mate! much clearer! will try it

ok all done! thanks guys

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.)