FIND GCD for m and n
·
//Assume m>= n
GCD( m,n)
{
If (n = 0)
return m
else
return GCD( m, n mod n)
}
·
CONSECUTIVE INTEGER CHECKING for computing gcd(m,n)
(step1) t =
min{m,n}
(step2) If (m mod t = 0)
{
If (n mod t = 0)
Return t;
Else
{Decrease t by 1; Go to step 2}
}
else
{Decrease t by 1; Go to step 2}
·
MIDDLE SCHOOL PROCEDURE (not an algorithm yet) to
determine gcd(m,n)
1. Find prime factors of m
2. Find prime factors of n
3. Identify all the common prime factors for both numbers.
If p appears 3 times in m, and appears 5 times in n, factor p should be taken 3 times ( or minimum of the number of times in each of the two)
4. Return the product of all the common factors.
Find
GCD(70, 42)
70 = 2 * 5 * 7 GCD = 14
42 = 2 * 3 * 7