JavaScript Program to Find HCF of Two Numbers

You can find the HCF of two numbers in JavaScript using the Euclidean algorithm with a function like function hcf(a, b) { while(b) { [a, b] = [b, a % b]; } return a; }.

Examples

Input12, 18

Output6

Input100, 25

Output25

Input7, 13

Output1

How to Think About It

To find the HCF of two numbers, repeatedly replace the larger number by the remainder when the larger is divided by the smaller until the remainder is zero. The last non-zero remainder is the HCF.

Algorithm

1

Get two numbers as input.

2

While the second number is not zero, do:

3

Replace the first number with the second number.

4

Replace the second number with the remainder of the first number divided by the second number.

5

When the second number becomes zero, return the first number as the HCF.

Code

javascript

function hcf(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

console.log(hcf(12, 18)); // Output: 6

Output

6

Dry Run

Let's trace hcf(12, 18) through the code

1

Initial values

a = 12, b = 18

2

First iteration

a = 18, b = 12 % 18 = 12

3

Second iteration

a = 12, b = 18 % 12 = 6

4

Third iteration

a = 6, b = 12 % 6 = 0

5

End loop

b is 0, return a = 6

a	b
12	18
18	12
12	6
6	0

Why This Works

Step 1: Use Euclidean algorithm

The algorithm uses the fact that the HCF of two numbers also divides their difference or remainder.

Step 2: Loop until remainder zero

We keep replacing the larger number with the remainder until the remainder is zero.

Step 3: Return last non-zero remainder

When remainder is zero, the other number is the HCF.

Alternative Approaches

Recursive Euclidean algorithm

javascript

function hcf(a, b) {
  if (b === 0) return a;
  return hcf(b, a % b);
}

console.log(hcf(12, 18)); // Output: 6

Uses recursion instead of loop; easier to read but may cause stack overflow for very large inputs.

Brute force method

javascript

function hcf(a, b) {
  let min = Math.min(a, b);
  for (let i = min; i > 0; i--) {
    if (a % i === 0 && b % i === 0) return i;
  }
}

console.log(hcf(12, 18)); // Output: 6

Checks all numbers from min down to 1; simple but inefficient for large numbers.

Complexity: O(log(min(a, b))) time, O(1) space

Time Complexity

The Euclidean algorithm runs in logarithmic time relative to the smaller input because each step reduces the problem size significantly.

Space Complexity

It uses constant extra space since it only stores a few variables and updates them in place.

Which Approach is Fastest?

The iterative Euclidean algorithm is fastest and most memory efficient compared to recursion or brute force.

Approach	Time	Space	Best For
Iterative Euclidean	O(log(min(a,b)))	O(1)	Large numbers, efficiency
Recursive Euclidean	O(log(min(a,b)))	O(log(min(a,b)))	Readability, small inputs
Brute Force	O(min(a,b))	O(1)	Very small numbers, simplicity