The greatest common divisor (GCD) or the highest common factor (HCF) of two numbers is the largest positive integer that perfectly divides the two given numbers. Solving this problem for a specific set of numbers is easy. For example, find the GCD of 12 and 18. The The divisors of 12 are 1, 2, 3, 4, 6, 12 and for 18 are 1, 2, 3, 6, 9, 18. The common factors are 1, 2, 3, and 6. So the greatest common factor is 6.
How would you find the GCD for any number? Here the problem is more challenging. Here is one solution. Let's take two integers a and b passed to a function which returns the GCD. In the function, we first determine the smaller of the two number since the GCD (HCF) can only be less than or equal to the smallest number. For example, the GCD of 12 and 14 can only be less than 12 and not greater. We then use a for loop to go from 1 to that number.
In each iteration, we check if our number perfectly divides both the input numbers. If so, we store the number as the GCD. At the completion of the loop we end up with the largest number that perfectly divides both the numbers.
Below is the algorithm in python.
def computeGCD(a, b):
if a < b:
smaller = a
smaller = b
for i in range(1, smaller+1):
if (a % i == 0) & (b % i == 0):
gcd = i
N.B: Do not cut and paste the above code. Make sure the indentation is correct.
The above method is easy to understand and implement but not efficient. A much more efficient method to find the GCD (HCF) is the Euclidean algorithm.
The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. That is a mouthful! Let's make it simple by taking an example. 21 is the GCD of 252 and 105 (as 252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 147 (252 − 105). Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers.
A more efficient version of the algorithm shortcuts these steps, instead we divide the greater by smaller and take the remainder. Now, divide the smaller by this remainder. Repeat until the remainder is 0.
For example, if we want to find the H.C.F. of 54 and 24, we divide 54 by 24. The remainder is 6. Now, we divide 24 by 6 and the remainder is 0. Hence, 6 is the required GCD.
Python code for Euclidean Algorithm
def euclidAlgo(a, b):
a, b = b, a % b
Python code for Euclidean Algorithm using recursion:
def euclidAlgo(a, b):
if (b == 0):
return euclidAlgo(b, a % b)
Sources: Wikipedia; https://www.programiz.com/python-programming/examples/hcf
Write something about yourself. No need to be fancy, just an overview.