C++ Program to Find HCF of Two Numbers

You can find the HCF of two numbers in C++ using the Euclidean algorithm with code like while(b != 0) { int temp = b; b = a % b; a = temp; } where a and b are the input numbers.

Examples

Inputa = 12, b = 18

Output6

Inputa = 100, b = 25

Output25

Inputa = 7, b = 3

Output1

How to Think About It

To find the HCF of two numbers, think about the largest number that divides both without leaving a remainder. The Euclidean algorithm helps by repeatedly replacing the larger number with the remainder of dividing the larger 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, the first number is the HCF.

6

Return or print the first number as the HCF.

Code

cpp

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cout << "Enter two numbers: ";
    cin >> a >> b;
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    cout << "HCF is " << a << endl;
    return 0;
}

Output

Enter two numbers: 12 18
HCF is 6

Dry Run

Let's trace the input a=12, b=18 through the code

1

Initial values

a = 12, b = 18

2

First iteration

temp = 18; b = 12 % 18 = 12; a = 18

3

Second iteration

temp = 12; b = 18 % 12 = 6; a = 12

4

Third iteration

temp = 6; b = 12 % 6 = 0; a = 6

5

Loop ends

b is 0, so HCF is a = 6

a	b	temp	b = a % b
12	18
18	12	18	12
12	6	12	6
6	0	6	0

Why This Works

Step 1: Why use the Euclidean algorithm?

The Euclidean algorithm efficiently finds the HCF by using the remainder operation % to reduce the problem size each step.

Step 2: How the loop works

Each loop iteration replaces the pair (a, b) with (b, a % b), moving closer to the HCF.

Step 3: When the loop ends

When b becomes zero, a holds the HCF because the remainder is zero, meaning a divides the original numbers.

Alternative Approaches

Recursive Euclidean Algorithm

cpp

#include <iostream>
using namespace std;

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

int main() {
    int a, b;
    cout << "Enter two numbers: ";
    cin >> a >> b;
    cout << "HCF is " << hcf(a, b) << endl;
    return 0;
}

This uses recursion instead of a loop, which can be cleaner but uses more stack memory.

Brute Force Method

cpp

#include <iostream>
using namespace std;

int main() {
    int a, b, hcf = 1;
    cout << "Enter two numbers: ";
    cin >> a >> b;
    int min = (a < b) ? a : b;
    for (int i = 1; i <= min; i++) {
        if (a % i == 0 && b % i == 0) {
            hcf = i;
        }
    }
    cout << "HCF is " << hcf << endl;
    return 0;
}

This checks all numbers up to the smaller input, which is simple but slower 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)))	Cleaner code, small inputs
Brute Force	O(min(a,b))	O(1)	Very small numbers, simplicity