Middle-school procedure for computing gcd (m, n)

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