What are the Advantages of Using Euclid's Algorithm? What are the advantages of using Euclid's algorithm over prime decomposition to find the gcd of two integers?
Should one use Euclid’s algorithm in some cases and prime decomposition in others?
 A: I just asked Wolfram alpha for three prime numbers $r$, $s$ and $t$ and calculated
$$
rs = 680112645959 
$$
and 
$$
rt =419449814461
$$
so $r$ is the greatest common divisor of those two products.
You can find $r$ pretty quickly by hand with the Euclidean algorithm. Factoring the numbers to do that is harder (unless you ask a computer program like Wolfram alpha to do the work for you).
A: The Euclidean Algorithm is generally considered to be an extremely fast way to find the greatest common divisor of a pair of integers. In fact, the Indian mathematician, Aryabhata called it "the pulverizer."
That being said, the algorithm operates slowly when, for example, it is used to find the gcd of a pair of successive Fibonacci numbers. And that is because the quotient in every step of the process except for the last is $1$. More specifically, it would take precisely $n$ divisions to show that the $gcd$ of the $(n+1)$st and $(n+2)$nd Fibonacci numbers is $1$.
In general though, Lame's Theorem provides us with an estimate of the number of divisions necessary to find the greatest common divisor; it says that the $gcd(a,b)$ does not exceed five times the number of decimal digits in the smaller of the two integers $a, b$.   
