How to find the greatest common factor (GCF) using Euclid's Algorithm

Darren Jones
May 6, 2021

The following function will find the greatest common divisor (GCD), also known as the highest common factor (HCF) of two numbers, a and b:

copy code
const gcd = (a,b) => b === 0 ? a : gcd(b,a%b)

This function uses the Euclidean algorithm by recursively finding the remainder when a is divided by b, until this value is zero (i.e. there is no remainder because the two numbers divide exactly into each other). The GCD that is returned is the last remainder that wasn’t zero.

For example, to find the GCD of 20 and 8, you would find the remainder when you divide 20 by 8, which is 4

You would then apply the function again using 8 and 4, so find the remainder when dividing 8 by 4, which is zero.

Because the answer is zero, we stop and

The GCD is the last remainder that wasn’t zero, which in this case is 4.

The function uses the ternary operator to check if the value of the second argument is equal to zero, if it is then it returns the first argument, if it isn’t it calls the function again, but uses the remainder operator to find the remainder from dividing the two arguments. This process continues until the remainder (the second argument) is zero, in which case the first argument (the previous remainder) is returned.

Know a better answer? Join our our community and let us know.