C Program to Find HCF of Two Numbers

You can find the HCF of two numbers in C by using the Euclidean algorithm with a loop: repeatedly replace the larger number by the remainder of dividing the larger by the smaller until the remainder is zero, then the smaller number is the HCF. For example, use while(b != 0) { int temp = b; b = a % b; a = temp; } where a and b are the two numbers.

Examples

Inputa = 12, b = 18

OutputHCF is 6

Inputa = 100, b = 25

OutputHCF is 25

Inputa = 7, b = 3

OutputHCF is 1

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 bigger number with the remainder when divided by the smaller number until the remainder is zero. The last non-zero remainder is the HCF.

Algorithm

1

Get input values for two numbers a and b

2

While b is not zero, do:

3

- Calculate remainder of a divided by b

4

- Replace a with b and b with the remainder

5

When b becomes zero, a contains the HCF

6

Return or print the value of a

Code

c

#include <stdio.h>

int main() {
    int a, b, temp;
    printf("Enter two numbers: ");
    scanf("%d %d", &a, &b);
    while (b != 0) {
        temp = b;
        b = a % b;
        a = temp;
    }
    printf("HCF is %d\n", a);
    return 0;
}

Output

Enter two numbers: 12 18
HCF is 6

Dry Run

Let's trace the input a=12 and 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 = a = 6

a	b	temp	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?

It efficiently finds the HCF by using division and remainder instead of checking all factors.

Step 2: How the loop works

Each loop replaces the larger number with the smaller and the smaller with the remainder, reducing the problem size.

Step 3: When the loop ends

When remainder becomes zero, the last non-zero smaller number is the HCF.

Alternative Approaches

Using subtraction method

c

#include <stdio.h>

int main() {
    int a, b;
    printf("Enter two numbers: ");
    scanf("%d %d", &a, &b);
    while (a != b) {
        if (a > b) a = a - b;
        else b = b - a;
    }
    printf("HCF is %d\n", a);
    return 0;
}

This method uses repeated subtraction instead of modulus; it is simpler but slower for large numbers.

Using recursion

c

#include <stdio.h>

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

int main() {
    int a, b;
    printf("Enter two numbers: ");
    scanf("%d %d", &a, &b);
    printf("HCF is %d\n", hcf(a, b));
    return 0;
}

This recursive approach is elegant and concise but uses function call stack.

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 modulus-based Euclidean algorithm is faster than subtraction and uses less memory than recursion.

Approach	Time	Space	Best For
Euclidean algorithm (modulus)	O(log(min(a,b)))	O(1)	Fast and efficient for all inputs
Subtraction method	O(min(a,b))	O(1)	Simple but slow for large numbers
Recursive Euclidean	O(log(min(a,b)))	O(log(min(a,b)))	Elegant code but uses stack space