Step 1 Find the prime factors of m.
Step 2 Find the prime factors of n.
Step 3 Identify all the common factors in the two prime expansions found in
Step 1 and Step 2. (If p is a common factor occurring Pm and Pn times
in m and n, respectively, it should be repeated min{pm, Pn} times.)
Step 4 Compute the product of all the common factors and return it as the
greatest common divisor of the numbers given.
Thus, for the numbers 60 and 24, we get
60
2.2.3.5
24
2.2 2.3
gcd (60, 24) = 2.2.3=12.
Nostalgia for the days when we learned this method should not prevent us
from noting that the last procedure is much more complex and slower than Euclid's
algorithm. (We will discuss methods for finding and comparing running times
of algorithms in the next chapter.) In addition to inferior efficiency, the middle-
school procedure does not qualify, in the form presented, as a legitimate algorithm.
Why? Because the prime factorization steps are not defined unambiguously: they
Fig: 1