Problem Solving: Computing GCD

In mathematics, the greatest common divisor (GCD) of two or more integers, is the largest positive integer that divides each of the integers.

For example,

Divisors of 8: 1, 2, 4, 8

Divisors of 16: 1, 2, 4, 8, 16

Divisors of 12: 1, 2, 3, 4, 6, 12

The GCD of 8, 16 and 12 is 4 because it is both a common divisor to each of them and the greatest of their common divisors. Sometimes, it is also called the highest common factor (HCF).

In this lesson, we will start with the most obvious solution and then tweak it till we get an efficient one. So let’s start!

Finding the GCD of two numbers

We need to determine the biggest number that divides the two numbers. We can make a function (let’s call it gcd()) that takes two integers n1, and n2 and determines the greatest number, which divides both numbers.