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

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

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?

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

gcd(a, b, c) == gcd(gcd(a, b), c)

gcd(a, b, c) == gcd(gcd(a, b), c)

Oops... that's right. Too much work today...

Greets,
Philip

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?

Originally Posted by Ideswa

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