Getting the highest common factor in JavaScript

It was a while ago when I posted a mathematics-related article, so here’s a short one again on finding the highest common factor and lowest common multiple of two positive integers.

First, let’s start with some maths background. If you are familiar with the concepts of the highest common factor and lowest common multiple, you can skip the coming section.

Background

A factor of a positive whole number is an integer which evenly goes into that number, i.e. there is no remainder after dividing the number by the factor.

For example, 3 is a factor of 12, because 12 / 3 = 4.

But 5 is not a factor of 12, because 12 / 5 = 2.4, i.e. the result is 2 with a remainder of 2.

If we consider two numbers, it’s possible that they have common factors: divisors that evenly go into both numbers.

For example, 3 is a factor of both 12 and 18, so it’s a common factor of 12 and 18.

Two numbers can have multiple common factors. The highest common factor (HCF) is the highest of all of these common factors.

The highest common factor of 12 and 18 is going to be 6, because both 12 and 18 are divisible by 6, and 6 is the greatest such number.

What if there are no common factors that are greater than 1? Consider 3 and 7. These numbers are called relative primes, and their HCF is 1.

The highest common factor is used in several areas of mathematics, like factorization or simplifying fractions. Finding the HCF is a very common high school (primary school) exercise.

On the other hand, a common multiple of two numbers is a number in which both numbers go evenly.

As example, let’s take 3 and 5. Common multiples of 3 and 5 are 15, 30, 45 etc., because both 3 and 5 go evenly into these numbers.

Two numbers have infinite common multiples, so it would take a while to list all of them (good luck if you give it a try).

Instead, we are often interested in the lowest of all common multiples, which we call the lowest common multiple (LCM). This number always exists.

If the two numbers are relative primes (like 3 and 5), the LCM will be the product of the numbers, so in this example, the LCM of 3 and 5 will be 15.

If they are not relative primes, we will need to divide the product of the two numbers by the HCF.

Probably the most common use case of the lowest common multiple is when two fractions need to be added or subtracted and the common denominator needs to be found.

OK, enough of maths, and if you are still here, and haven’t hit your head against a wall, we can move on to the JavaScript implementation of the HCF and LCM.

Find the highest common factor

Let’s break down the problem to smaller pieces first.

Breakdown of the problem

If one of the numbers is divisible by the other number, we have found the HCF, and this is going to be the divisor (i.e. the smaller number). For example, 3 is a divisor of 12, so 3 is the HCF of both.

Furthermore, it only makes sense to search for the HCF up to the half of the smaller number. This is because the smallest number by which any number may be divisible with is 2 (ignore 1 here) and that will give us the half of the number (given our number is even).

So we can set an upper limit of the half of the smaller number for our search.

Finally, we can search for the HCF by checking if each number up to our upper limit is a divisor of both numbers and get the highest of these divisors.

Implementation

Let’s start by creating a function called getHCF. This function will accept two arguments, the two numbers which we want to find the highest common factor of:

function getHCF(a, b) {
  // code comes here
}

The first step is to check if one of the numbers is divisible by the other. If so, we have found the HCF, and it’s going to be the smaller i.e. the minimum of the two numbers.

It makes sense to find the minimum of a and b, and store this value in a variable. Then min will be returned as the HCF in this first scenario:

function getHCF(a, b) {
  const min = Math.min(a, b);
  if (b % a === 0 || a % b === 0) return min;
}

We can use the Math.min method to find the smaller of the two numbers and the % modulo operator checks if a and b are divisors of each other. This will occur if the remainder is zero.

Unluckily, this is not enough in most cases, because a won’t always be divisible by b or vice versa. What’s more, it’s possible that they don’t even have a common factor which is greater than 1, i.e. they are relative primes.

So it’s a good idea to declare a hcf variable and assign 1 to it, then find the limit for our search:

function getHCF(a, b) {
  const min = Math.min(a, b);
  if (b % a === 0 || a % b === 0) return min;

  let hcf = 1;
  const limit = Math.floor(min / 2);

  for (let i = 1; i <= limit; i++) {
    if (a % i === 0 && b % i === 0) hcf = i;
  }

  return hcf;
}

As discussed above, limit is the half of the smaller number (min) up to which we search for common factors.

As we don’t know if min is odd or even, we can use the Math.floor method, which takes the whole part of any decimal (i.e. it “rounds” it down to the nearest integer).

The search for the common factors occur inside the for loop. If any i smaller than or equal to min is the divisor of both a and b, then it will definitely be a common factor, and we override the current value of hcf by assigning i to it.

If no such i is found, it means that a and b are relative primes and the value of hcf will remain 1.

Lowest common multiple

This one is even easier. We need to find one number (the smallest of the common multiples).

If the two numbers, a and b are relative primes (i.e. the HCF is equal to 1), we simply multiply them together.

If not, the product of a and b needs to be divided by the HCF, and the result is going to be the LCM.

In both cases, we’ll need the HCF. Why not use the getHCF function defined above?

function getLCM(a, b) {
  const hcf = getHCF(a, b);

  return hcf === 1 ? (a * b) : (a * b / hcf);
}

First, get the HCF of a and b. If it’s equal to 1 (this means that a and b are relative primes), we return the product of a and b.

If they are not relative primes, we divide a * b by the hcf and return the result.

This can be nicely done using a ternary operator. The parentheses are only there for readability purposes.

That’s it!

Conclusion

Some mathematics is needed to find functions that calculate the highest common factor and the lowest common multiple of two numbers.

As always, breaking down the problem to smaller pieces helps construct the functions.

Thanks for reading, and see you next time.