Finding the HCF of a pair of numbers with JavaScript
The highest common factor is the largest number which divides two numbers exactly. For example the HCF of 20 and 12 is 4.
This function uses Euclid's algorithm to find the highest common factor of a pair of numbers. The algorithm works as follows:
- Find the remainder when dividing the largest by the smallest number
- Set the larger number equal to this remainder
- Repeat steps 1 and 2 until the remainder is zero.
- The smaller number is the HCF of the two original numbers.
The function checks the inputs are both positive integers before performing the algorithm.
function findHCF(x, y) {
// If the input numbers are less than 1 return an error message.
if (x < 1 || y < 1) {
return "Please enter values greater than zero.";
}
// If the input numbers are not integers return an error message.
if (x != Math.round(x) || y != Math.round(y)) {
return "Please enter whole numbers.";
}
// Now apply Euclid's algorithm to the two numbers.
while (Math.max(x, y) % Math.min(x, y) != 0) {
if (x > y) {
x %= y;
}
else {
y %= x;
}
}
// When the while loop finishes the minimum of x and y is the HCF.
return Math.min(x, y);
}
The function can also be nested to find the highest common factor of 3 or more values. For example:
var x = findHCF(findHCF(24, 72), 160);
will assign x = 8.
Use the code to find the HCF of a pair of numbers.
See the code in action below. Choose two positive integers and click 'Find HCF' to find the highest common factor.
Enter a pair of numbers into the boxes above.