How to evaluate the greatest common divisor?

Apr 2008
50
0
What are the advantages of using Euclid's algorithm over prime decomposition to find the gcd of two numbers?
Should you use Euclid’s algorithm in some cases and prime decomposition in others?
 
Aug 2007
3,171
860
USA
What operations are required to perform each method?

You'll have to generalize with specific difficult examples.'
1) Lot's of repetitions of the same prime factor.
2) Very large prime factors.
3) Other interesting things.