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; } which returns a as the HCF.

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, 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. This works because the HCF divides both numbers evenly.

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 the first number as the HCF.

Code

csharp

using System;
class Program {
    static void Main() {
        int a = 12, b = 18;
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        Console.WriteLine("HCF is " + a);
    }
}

Output

HCF is 6

Dry Run

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

a	b	temp	b after modulo
12	18	18	12
18	12	12	6
12	6	6	0

Why This Works

Step 1: Using Euclidean Algorithm

The code uses the Euclidean algorithm which finds HCF by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller.

Step 2: Loop until remainder zero

The loop continues until the remainder (b) becomes zero, meaning the last non-zero remainder is the HCF.

Step 3: Return the HCF

When the loop ends, the variable a holds the HCF which is printed as the result.

Alternative Approaches

Recursive Euclidean Algorithm

csharp

using System;
class Program {
    static int HCF(int a, int b) {
        if (b == 0) return a;
        return HCF(b, a % b);
    }
    static void Main() {
        Console.WriteLine("HCF is " + HCF(12, 18));
    }
}

This uses recursion instead of a loop, making the code shorter but uses call stack.

Using for loop and checking divisors

csharp

using System;
class Program {
    static void Main() {
        int a = 12, b = 18, hcf = 1;
        int min = a < b ? a : b;
        for (int i = 1; i <= min; i++) {
            if (a % i == 0 && b % i == 0) hcf = i;
        }
        Console.WriteLine("HCF is " + hcf);
    }
}

This checks all numbers up to the smaller number, less efficient but easy to understand.

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

Time Complexity

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

Space Complexity

The algorithm uses constant extra space as it only stores a few variables and updates them in place.

Which Approach is Fastest?

The Euclidean algorithm (iterative or recursive) is much faster than checking all divisors, especially for large numbers.

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)))	Clean code, small inputs
Divisor Checking	O(min(a,b))	O(1)	Small numbers, simplicity