Euclidean Algorithm for app-codility-com-programmers Explained in Cpp
Category of Article
By: Chrysanthus Date Published: 10 Sep 2025
This lesson (tutorial) explains fast ways to find the Greatest Common Divisor (Highest Common Factor) and the Least Common Multiple. However, first, Division has to be explained.
Division
The general statement for division is:
Dividend ÷ Divisor = Quotient
The quotient can have a remainder. Division means, the number of times the divisor will go into a dividend. For example, the number of times 2 will go into 6 is 3. That is:
2 + 2 + 2 = 6
Or put another way,
6 = 2 + 2 + 2
This is conveniently written as:
6 ÷ 2 = 3
As another example, the number of times, 3 will go into 13, is 4 remainder 1. That is:
3 + 3 + 3 + 3 + 1 = 13
Or put another way,
13 = 3 + 3 + 3 + 3 + 1
This is conveniently written as:
13 ÷ 3 = 4 R 1
where R means remainder.
The long division method learned in school, is one way to do division. Though that method looks easier to understand, it has many operations (steps). In other words, the algorithm is long. Many operations mean high time complexity. There are shorter algorithms; such as the division by subtraction algorithm below:
Division by Subtraction
Dividing 6 by 2 by subtraction is done as follows:
6 - 2 = 4
4 - 2 = 2
2 - 2 = 0
The number of steps (statements) are counted, and the answer for the division are those number of steps. The divisor is first subtracted from the dividend to give a difference. In this case, 2 is subtracted from 6 to give 4. Next, the same divisor number is subtracted from the difference to have a new difference. This subtraction scheme continues until the difference is either 0 or smaller than the divisor. The number of operations (steps) is the quotient (answer). Any last difference, which is not 0 and is less than the divisor, is the remainder. Zero can be considered as a special kind of remainder, which is just zero. The following division by subtraction, shows steps (operations) ending with a remainder:
13 – 3 = 10
10 – 3 = 7
7 – 3 = 4
4 – 3 = 1
The number of statements (steps) is 4 and the remainder is 1. So the quotient (answer) is 4 remainder 1. Division by subtraction is faster than division by the long division method (taught in schools).
Highest Common Factor
Among all the factors for two integers, the one with the highest value that is common to both integers, is known as the Highest Common Factor. Both integers are divisible by this factor. The Highest Common Factor, abbreviated HCF is also called the Greatest Common Divisor, abbreviated, GCD.
Example Question
Find the highest common factor for the numbers 40 and 100, using its name, Highest Common Factor (from first principles).
Solution:
The factors of 40 and 100 are:
40: 2, 4, 5, 8, 10, 20, 40
100: 2, 4, 5, 10, 20, 25, 50, 100
The common factors are:
2, 4, 5, 10, 20
The highest of these common factors is:
20
Writing a program to find the HCF, this brute-force way, needs too many operations, implying high time complexity. A lower time complexity can be achieved using a modified division-by-subtraction approach.
GCD Algorithm for Modified Division-by-Subtraction
Begin by subtracting the smaller number (subtrahend) from the bigger number (minuend) to have the first difference. Next, between the subtrahend and the difference, subtract the smaller number from the greater number, to have a new difference. Repeat this next step for different results (differences) until the result is zero. The last minuend, which is equal to the last subtrahend, is the highest common factor (greatest common divisor).
Example
The greatest common factor between 40 and 100, is obtained using the Algorithm for Modified Division-by-Subtraction, as follows:
100 - 40 = 60
60 - 40 = 20
40 - 20 = 20
20 - 20 = 0
There are just four steps here. The HCF is 20, at the last step.
If the last minuend is 1, with final difference 0, then the given two numbers do not have an HCF greater than 1. In this case the HCF is 1.
Programming Code for GCD Algorithm with Modified Division-by-Subtraction
The reader should read through the following program and its comments:
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (a == b) //indirect last step
return a;
if (a > b)
return gcd(a-b, b); //subtrahend minus difference; two arguments
else
return gcd(a, b-a); //difference minus subtrahend; two arguments
}
int main (int argc, char ** argv)
{
int ret = gcd(100, 40);
cout << ret << endl;
return 0;
}
The output is 20. The time complexity for this is:
O(n) = O(a+b)
gcd() is a recursive function, which is a function that calls itself in at least one of the statements in its body.
Greatest Common Divisor by Modulus
Example Question
Find the greatest common divisor for the numbers 60 and 108, using its name (from first principles), Greatest Common Divisor (Highest Common Factor).
Solution:
The divisors (factors) without remainder, of 60 and 108 are:
60: 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
108: 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108
The common divisors (factors) are:
2, 3, 4, 6, 12
The highest of these common divisors (factors) is:
12
Writing a program to find the GCD, this brute-force way, needs too many operations, implying high time complexity. A lower time complexity can be achieved using another approach, which is the modulus approach below:
Modulus
When the dividend is divided by the divisor, there is a quotient with a remainder. The remainder might be zero. The modulus is the remainder, when the dividend is divided by the divisor. The modulo, symbol for this operation, is % and not ÷ . That is:
Dividend % Divisor = remainder
For example,
108 % 60 = 48
because
108 ÷ 60 = 1 R 48
Algorithm for Modulus Approach
Begin by dividing the given bigger number (dividend) by the given smaller number (divisor) to obtain the remainder. Next, divide the divisor by the remainder, to have a new remainder. Repeat this next step for different results (remainders) until the remainder is zero. The last divisor, is the highest common factor (GCD).
Example 1
The greatest common divisor between 60 and 108, is obtained using the Modulus Algorithm, as follows:
108 % 60 = 48 //108 ÷ 60 = 1 R 54
60 % 48 = 12 //60 ÷ 48 = 1 R 12
48 % 12 = 0 //48 ÷ 12 = 4 R 0
The GCD is 12, the divisor at the last step.
If the last divisor is 1, with final quotient 0 (i.e. 0R0), then the given two numbers do not have an HCF (GCD) greater than 1. In this case the HCF is 1.
Example 2
Find the highest common factor between 24 and 9, from first principles; and then find it using the Modulus Algorithm.
Solution:
From first principles:
The factors of 24 and 9 are:
24: 2, 3, 4, 6, 8, 24
9: 3, 3
There is only one common factor, which is just:
3
So, the highest common factor is still:
3
Using the Modulus Algorithm:
24 % 9 = 6 //24 ÷ 9 = 2 R 6
9 % 6 = 3 //9 ÷ 6 = 1 R 3
6 % 3 = 0 //6 ÷ 3 = 2 R 0
The HCF is 3, the divisor at the last step.
Programming Code for GCD Algorithm with Modulus Approach
The reader should read through the following program and its comments:
#include <iostream>
using namespace std;
int gcdM(int a, int b) {
if (a % b == 0) //indirect last step
return b;
else
return gcdM(b, a % b); //divisor mod remainder, two arguments
}
int main (int argc, char ** argv)
{
int ret = gcdM(108, 60);
cout << ret << endl;
return 0;
}
The GCD (HCF) is 12. The time complexity for this is logarithmic, that is:
O(log(a + b))
which is better than the above linear time of O(a+b) = O(n). A division here, is considered as one main operation.
gcdM() is a recursive function, which is a function that calls itself in at least one of the statements in its body.
Least Common Multiple
LCM stands for Least Common Multiple. The least common multiple (LCM) of two integers ‘a’ and b, is the smallest positive integer that is divisible by both a and b.
Example Question
Find the LCM of 40 and 50, from your understanding of LCM.
Solution:
Multiples of 40 and 50 are:
40: 40, 80, 120, 160, 200, 240, 280, 320, 360, 400, 440, 480, 520, 560, 600, etc.
50: 50, 100, 150, 200, 250, 300, 350, 400, 450, 500, 550, 600, etc.
Common multiples of 40 and 50 are:
200, 400, 600
The least of these common multiples is:
200
The answer is 200.
Finding the LCM as just done, takes a lot of operations. There is a relationship between HCF and the product of the given numbers, such as 40 and 50, that can be taken advantage of, leading to a lower number of operations (see below).
Relationship between HCF and the Product of the Given Numbers
HCF Using Factors
The HCF of 40 and 50 can be obtained by prime factors as follows:
40 = 2 x 2 x 2 x 5
50 = 2 x 5 x 5
The prime factors that are common in 40 and 50, without repetition, are:
2 x 5 //given as multiplication
The product is:
10
The HCF of 40 and 50 is 10.
Product of 40 and 50
The product of 40 and 50 is:
40 x 50 = 2000
Product of 40 and 50 divided by HCF
The product of 40 and 50 divided by the HCF, 10 is:
2000 ÷ 10 = 200
Note that this is the LCM of 40 and 50. The LCM can be obtained in the following way:
40 and 50 can be written as the multiplication of their prime factors. Ten, the HCF can also be written as the multiplication of its prime factors. The LCM of 40 and 50 can thus be expressed as follows:
which is equivalent to the previous statement. The factors that are the same, above and below the division line, cancel out, to result in 200.
In general, the LCM of any two given numbers, can be obtained by dividing the product (multiplication) of the given numbers, by their HCF. This can be written as follows:
where the dot means multiplication, and gcd stands for Greatest Common Divisor (same as HCF). The shortest way to find the HCF should be used.
This is a fast way (has fewer operations) to obtain the LCM, than the method above. The time complexity for this is:
O(log(a+b))
The operation count for a.b and the operations count for dividing that product by gcd(a.b), are ignored (these two set of operations, for the total number of operations for this official LCM time complexity, are ignored).
Fast Program to Determine the LCM
The following is a fast program to determine the LCM. It divides the product of the numbers given, by the GCD (HCF), obtained using the modulus approach.
#include <iostream>
using namespace std;
int gcdM(int a, int b) {
if (a % b == 0) //indirect last step
return b;
else
return gcdM(b, a % b); //divisor mod remainder
}
int lcm (int a, int b) {
int lcm = (a*b) / gcdM(a,b);
return lcm;
}
int main (int argc, char ** argv)
{
int ret = lcm(40, 50);
cout << ret << endl;
return 0;
}
The output is 200, as expected, and done fast.
LCM for More than 2 Variables
Assume that the variables whose LCM are needed, are: a1,, a2, a3, then the equation to determine the LCM becomes:
LCM = lcm(a1, lcm(a2, a3))
If there are four variables, a1,, a2, a3, a4, then the equation would be:
LCM = lcm(a1, lcm(a2 lcm(a3, a4)))
If there are five variables, a1,, a2, a3, a4, a5, then the equation would be:
LCM = lcm(a1, lcm(a2, lcm(a3 lcm(a4, a5))))
and so on.
Exercise
Problem: Michael, Mark and Matthew collect coins of consecutive face values a, b and c
(each boy has only one kind of coins). The boys have to find the minimum amount of money
that each of them may spend by using only their own coins. (Hint: lcm(a, b, c) )
Note: The number of a's for Michael are infinite. The number of b's for Mark are infinite. The number of c's for Michael are infinite.
Solution: The least common multiple of the three integers, i.e. lcm(a, b, c), is what is to be looked for. The program is:
#include <iostream>
using namespace std;
int gcdM(int a, int b) {
if (a % b == 0) //indirect last step
return b;
else
return gcdM(b, a % b); //divisor mod remainder
}
int lcm (int a, int b, int c) {
int lcm2 = (b*c) / gcdM(b,c);
int lcm1 = (a*lcm2) / gcdM(a,lcm2);
return lcm1;
}
int main (int argc, char ** argv)
{
int ret = lcm(25, 40, 50);
cout << ret << endl;
return 0;
}
The output is 200, and correct. We simply find the lcm n times, and each step works in logarithmic time.
Conclusion
Division can be done by repeated subtraction, with the subtrahend from the minuend first, and then for the rest of the operations, subtrahend from the difference. The whole number part of the quotient, is the total number of subtractions (number of times subtraction took place), including the first. The subtraction ends when the difference is less than the subtrahend. That difference is the remainder. The time complexity for this HCF approach is, O(n) = O(a+b), where a and b are the given numbers.
The HCF can also be obtained by repeated modulus operation, between the new divisor as dividend and former remainder, after the first modulus operation between the given dividend and given divisor (the two given numbers whose HCF is needed). The final remainder is always 0, and the last divisor is the HCF. The time complexity for this HCF approach is, O(log(a + b)) which is better than the above linear time of O(a+b) = O(n).
In order to obtain the LCM, the fast way, use:
where gcd is HCF, as HCF means the same as GCD. The time complexity for this LCM approach, is O(log(a+b)) .