Find GCD (HCF) in C#

Beginner
⏱️ 8 min read
📚 Updated: Jul 2026
🎯 2 Code Examples
Euclidean algorithm

What you’ll learn

  • What GCD (greatest common divisor / HCF) means and why it matters in fractions and number theory.
  • The classic Euclidean algorithm with a while loop — the standard C# interview answer.
  • A recursive version of the same idea, plus how GCD connects to LCM and common divisors.

Overview

GCD is a staple interview math problem. The Euclidean algorithm replaces repeated subtraction with modulo steps, finishing in logarithmic time. You will also see when to use Math.Abs and how to handle zeros.

Two programs

Iterative Euclidean loop and recursive gcd for comparison.

Live preview

Type two integers and watch the Euclidean steps compute GCD.

Real uses

Simplify fractions, find LCM, and list all common divisors efficiently.

Prerequisites

Integer division, modulo (%), and while loops in C#.

  • C# basics: static methods, Console.WriteLine, string interpolation.
  • Know that a % b is the remainder after dividing a by b.

What is GCD?

The greatest common divisor (GCD) — also called the highest common factor (HCF) — of two integers is the largest positive whole number that divides both without a remainder.

For 48 and 18, the common divisors are 1, 2, 3, and 6. The largest is 6, so gcd(48, 18) = 6.

gcd(48,18) 6
Divisors 1, 2, 3, 6
LCM link a*b/gcd

Euclidean definition

For integers a and b with b ≠ 0: gcd(a, b) = gcd(b, a mod b). Repeat until the second argument is 0; the GCD is the remaining first argument. Example trace for 48 and 18:

Steps

gcd(48,18) → gcd(18,12) → gcd(12,6) → gcd(6,0) = 6

Quick examples

gcd(12,8) 4
Share
Both divisible by 4
gcd(9,10) 1
Name
Coprime (relatively prime)

Takeaway: GCD finds the biggest shared factor — useful to reduce 12/18 to 2/3 by dividing top and bottom by 6.

Live preview

Enter two integers. The widget runs the Euclidean algorithm and shows each step.

Try 48 and 18, or 12 and 8.

Live result
Press “Compute GCD” to run the Euclidean steps.

Algorithm

Goal: compute gcd(a, b) for integers using the Euclidean method.

Normalize

Work with a = Math.Abs(a) and b = Math.Abs(b). Handle (0,0) separately if needed.

Loop while b ≠ 0

Save temp = b, set b = a % b, set a = temp.

Return a

When b becomes 0, a holds the GCD.

📜 Pseudocode

Pseudocode
function gcd(a, b):
    a = absolute value of a
    b = absolute value of b
    while b != 0:
        temp = b
        b = a mod b
        a = temp
    return a
1

Iterative Euclidean GCD

Classic reference solution: FindGCD uses a while loop with modulo. Sample inputs 48 and 18 print GCD 6.

c#
using System;

class Program
{
    static int FindGCD(int num1, int num2)
    {
        num1 = Math.Abs(num1);
        num2 = Math.Abs(num2);

        while (num2 != 0)
        {
            int temp = num2;
            num2 = num1 % num2;
            num1 = temp;
        }

        return num1;
    }

    static void Main()
    {
        int number1 = 48;
        int number2 = 18;

        int gcd = FindGCD(number1, number2);
        Console.WriteLine($"GCD of {number1} and {number2} is: {gcd}");
    }
}

Explanation

Each loop iteration shrinks the problem: gcd(48,18) becomes gcd(18,12), then gcd(12,6), then gcd(6,0)=6.

num2 = num1 % num2;

Remainder step. This is the heart of the Euclidean algorithm.

2

Recursive Euclidean GCD

Same math, expressed recursively: gcd(a,b) = gcd(b, a % b) until b == 0.

c#
using System;

class Program
{
    static int GcdRecursive(int a, int b)
    {
        a = Math.Abs(a);
        b = Math.Abs(b);

        if (b == 0)
            return a;

        return GcdRecursive(b, a % b);
    }

    static void Main()
    {
        int number1 = 48;
        int number2 = 18;

        Console.WriteLine($"GCD of {number1} and {number2} is: {GcdRecursive(number1, number2)}");
    }
}

Explanation

The base case b == 0 returns a. Otherwise the method delegates to a smaller pair — elegant, but uses call-stack depth proportional to the number of steps.

Beyond the basics

Binary GCD (Stein). Uses shifts and subtraction; can be faster for very large integers on some hardware.

LCM. lcm(a,b) = Math.Abs(a / gcd(a,b) * b) — divide first by gcd to reduce overflow risk when computing LCM.

Interview: write the modulo loop first, mention recursion as an alternative, then link GCD to simplifying fractions or finding LCM.

❓ FAQ

The GCD of two integers is the largest positive integer that divides both numbers with no remainder. It is also called HCF (highest common factor).
Repeatedly replace the larger number with the remainder of dividing the larger by the smaller: gcd(a,b) = gcd(b, a % b). Stop when the second number becomes 0; the first number is the GCD.
6. Both 48 and 18 are divisible by 1, 2, 3, and 6; 6 is the largest such value.
In C#, use Math.Abs on inputs before the loop so you work with magnitudes. gcd(-48, 18) = 6.
For a != 0, gcd(|a|, 0) = |a|. If both are 0, gcd is undefined in many definitions — handle (0,0) as a special case.
For positive a and b: lcm(a,b) = (a * b) / gcd(a,b). GCD interviews often lead to LCM follow-ups.
O(log min(|a|,|b|)) divisions — much faster than checking every candidate divisor up to min(a,b).

🔄 Input / output examples

Change number1 and number2 in Main, or read from console after validation.

abgcd(a,b)
48186
1284
9101
077

Edge cases and pitfalls

GCD is forgiving once you normalize signs — except the all-zero corner case.

Zero

gcd(0, n)

Returns |n|. gcd(0,0) is undefined — return 0 or throw with a comment.

Negatives

gcd(-48, 18)

Use Math.Abs so the answer stays positive (6).

Equal

gcd(n, n)

Returns |n| — both numbers share all of their divisors.

Order

gcd(a,b) vs gcd(b,a)

Same result — GCD is commutative.

⏱️ Time and space complexity

VersionTimeExtra space
Iterative EuclideanO(log min(|a|,|b|))O(1)
Recursive EuclideanO(log min(|a|,|b|))O(log min(|a|,|b|)) stack
Naive scan 1..minO(min(|a|,|b|))O(1)

The Euclidean algorithm is the efficient standard; naive divisor scanning is only for tiny teaching examples.

Summary

  • Definition: GCD is the largest positive integer dividing both inputs.
  • C#: Euclidean while (b != 0) loop with a % b — add Math.Abs for negatives.
  • Next step: list all common divisors via common divisors or compute LCM from GCD.
Did you know?

The Euclidean algorithm for GCD is one of the oldest algorithms still in daily use — Euclid described the idea around 300 BCE. In interviews, the iterative while (b != 0) version is what most hiring pairs expect first.

About the author

Mari Selvan M P
Mari Selvan M P 🔗

Developer, cloud engineer, and technical writer

  • Experience 12 years building web and cloud systems
  • Focus Full Stack Development, AWS, and Developer Education

I write practical tutorials so students and working developers can learn by doing—from databases and APIs to deployment on AWS.

AWS Certified Developer – Associate (Credly)

7 people found this page helpful

C# Program to Display Fibonacci Series C# Program to Check Happy Number