Find Common Divisors in C#

Beginner

⏱️ 10 min read

📚 Updated: May 2026

🎯 2 Code Examples

Number theory

What you’ll learn

What common divisors are and how they relate to gcd(a, b).
A straight loop to min(a, b) (classic style) and a gcd-first listing of divisors of g.
A browser live preview, plus edge cases (zeros, signs) and complexity notes for interviews.

Overview

Given two integers, list every positive integer that divides both. The naive approach tries each i from 1 up to the smaller nonnegative input; a tighter idea prints divisors of g = gcd(|a|,|b|).

Two programs

Double test each i, then Euclidean gcd plus divisor scan of g.

Live preview

Enter two integers and see common divisors (gcd path in JavaScript).

Interview polish

State the gcd characterization, handle (0,0), and mention O(√g) divisor tricks when g is huge.

Prerequisites

Integer remainder (%), for loops, and the idea that d divides n when n % d == 0.

using System;, Console.Write, and a static void Main() entry point.
Math.Abs((long)x) when you need magnitudes without int.MinValue overflow.

What are common divisors?

A divisor of n is a positive integer d such that n % d == 0. A common divisor of a and b is a positive d that divides both.

Divisors of 12 are 1, 2, 3, 4, 6, 12; divisors of 18 are 1, 2, 3, 6, 9, 18. The overlap is 1, 2, 3, 6—the common divisors.

Naive test each i

GCD list D(g)

Largest gcd itself

GCD characterization

Let g = gcd(|a|,|b|) for integers a, b not both zero. The set of positive common divisors of a and b equals the set of positive divisors of g.

24 and 36

gcd(24, 36) = 12. Divisors of 12 are 1, 2, 3, 4, 6, 12—exactly the sample output.

Intuition

12 & 18 gcd 6

Common: 1, 2, 3, 6

24 & 36 gcd 12

Common: 1, 2, 3, 4, 6, 12

Takeaway: common divisors are “shared factors”; the gcd is the largest of them.

Live preview

Two integers (JavaScript safe range). Euclidean gcd, then positive divisors of g. (0, 0) is flagged as ambiguous.

Algorithm

Goal: print all positive integers d such that a % d == 0 and b % d == 0.

Naive scan

For two nonnegative inputs, let m = min(a, b). For i from 1 to m, if both remainders are zero, print i.

Gcd route

Compute g = gcd(|a|,|b|). For each i from 1 to g, if g % i == 0, print i.

Euclidean gcd (core loop)

While b ≠ 0: replace (a, b) with (b, a % b). The last nonzero a is the gcd of the starting pair (up to sign).

📜 Pseudocode

Pseudocode (naive)

function printCommonDivisorsNaive(a, b):
    m ← min(a, b)   // nonnegative assumed
    for i from 1 to m:
        if a mod i = 0 and b mod i = 0:
            output i

Pseudocode (via gcd)

function gcd(|a|, |b|):  // Euclidean
    while b ≠ 0:
        (a, b) ← (b, a mod b)
    return a

function printCommonDivisorsGcd(a, b):
    g ← gcd(|a|, |b|)
    for i from 1 to g:
        if g mod i = 0:
            output i

Naive scan up to `min(a, b)`

Classic teaching flow: loop from 1 to the smaller input and print when both remainders are zero. Assumes nonnegative 24 and 36 like the original walkthrough.

using System;

class Program
{
    static void FindCommonDivisors(int num1, int num2)
    {
        Console.Write($"Common divisors of {num1} and {num2} are: ");

        int limit = num1 < num2 ? num1 : num2;

        for (int i = 1; i <= limit; i++)
        {
            if (num1 % i == 0 && num2 % i == 0)
            {
                Console.Write($"{i} ");
            }
        }

        Console.WriteLine();
    }

    static void Main()
    {
        int number1 = 24;
        int number2 = 36;

        FindCommonDivisors(number1, number2);
    }
}

Explanation

When both numbers are positive, no common divisor exceeds min(num1, num2), so the loop bound is safe.

if (num1 % i == 0 && num2 % i == 0)

Divisibility test. Both must agree on the same i.

Euclidean gcd, then divisors of `g`

Uses Math.Abs((long)x) so negatives follow the positive-divisor convention and int.MinValue does not overflow Math.Abs(int). Handles (0, 0) explicitly.

using System;

class Program
{
    static long GcdNonneg(long a, long b)
    {
        while (b != 0)
        {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    static void PrintDivisorsAscending(long g)
    {
        for (long i = 1; i <= g; i++)
        {
            if (g % i == 0)
            {
                Console.Write($"{i} ");
            }
        }
    }

    static void FindCommonDivisorsViaGcd(int num1, int num2)
    {
        long a = Math.Abs((long)num1);
        long b = Math.Abs((long)num2);

        Console.Write($"Common divisors of {num1} and {num2} are: ");

        if (a == 0 && b == 0)
        {
            Console.WriteLine("(undefined: every nonzero d divides 0)");
            return;
        }

        long g = GcdNonneg(a, b);
        PrintDivisorsAscending(g);
        Console.WriteLine();
    }

    static void Main()
    {
        FindCommonDivisorsViaGcd(24, 36);
        FindCommonDivisorsViaGcd(-12, 18);
    }
}

Explanation

Divisors of g match the positive common divisors once signs are stripped.

Math.Abs((long)num1)

Safe magnitude. Avoids OverflowException from Math.Abs(int.MinValue).

GcdNonneg(a, b)

Euclidean gcd. Short logarithmic-style iteration count in practice.

Optimization

Divisors of g. Loop i to √g: when g % i == 0, collect i and g / i, then sort if you need ascending output.

Beyond int. If inputs can exceed int, carry long (or BigInteger) through gcd and divisor listing.

Interview: state the gcd characterization before coding; mention (0,0) and sign conventions.

❓ FAQ

What is a common divisor of two numbers?

A positive integer d is a common divisor of a and b if d divides both a and b (remainder zero). Example: common divisors of 12 and 18 are 1, 2, 3, and 6.

Why does scanning only up to min(a,b) work for two positive numbers?

Any common divisor cannot exceed the smaller positive value: if d divides both and both are positive, then d is at most min(a, b).

How does gcd help?

The positive common divisors of a and b are exactly the positive divisors of g = gcd(|a|,|b|). Compute g with the Euclidean algorithm, then list divisors of g—often fewer iterations than testing every i against both original numbers.

What about negative inputs?

Divisibility depends on magnitude: use absolute values for the gcd path so you still list positive common divisors.

What if one number is 0?

gcd(|a|, 0) = |a|. The positive divisors of |a| are the positive common divisors of a and 0. If both are 0, every nonzero integer divides both in theory; practical programs treat (0, 0) as a special case.

Does C# have a built-in gcd?

.NET does not put gcd on int in the BCL for all targets; the Euclidean loop in Example 2 is standard interview code. Numerics-heavy libraries may offer helpers.

What is the time complexity?

Naive: O(min(|a|,|b|)) trials for positive inputs. Euclidean gcd is O(log min(|a|,|b|)); listing divisors of g is O(g) in the simple loop, or O(√g) with a pair enumeration.

🔄 Input / output examples

Swap number1 and number2 in Example 1, or add more calls in Example 2’s Main.

num1	num2	Common divisors (positive)
`24`	`36`	`1 2 3 4 6 12`
`12`	`18`	`1 2 3 6`
`7`	`11`	`1`
`0`	`100`	Divisors of `100` (gcd path)

Edge cases and pitfalls

The naive loop assumes nonnegative inputs; negatives and zeros need a clear policy.

Sign

Negative inputs

Example 1 is easiest with nonnegative values only. Example 2 uses absolute values so the divisor list stays positive.

Zero

One operand is zero

gcd(|a|, 0) = |a|. Example 1’s bound becomes 0 if min is literal—handle that separately.

Both zero

`(0, 0)`

Every nonzero d divides both; there is no finite complete list. Print a message or use an error code.

C# detail

`int.MinValue`

Math.Abs(int.MinValue) overflows an int. Cast to long first (as in Example 2).

⏱️ Time and space complexity

Approach	Time	Extra space
Naive scan to `min(a, b)` (nonnegative)	`O(min(a, b))`	`O(1)`
Euclidean gcd + divisor loop to `g`	`O(log min(\|a\|,\|b\|)) + O(g)`	`O(1)`
Divisors of `g` via `√g` scan	`O(log min + √g)` listing time	`O(1)` extra (excluding output)

Space excludes the printed sequence; only a few locals are needed.

Summary

Math: positive common divisors of a and b are the positive divisors of gcd(|a|,|b|) (except the pathological (0,0) case).
Code: naive double % check, or gcd then list divisors of g.
Watch-outs: nonnegative assumption in Example 1, (0,0), and Abs on int.MinValue.

Did you know?

Every common divisor of a and b divides gcd(a, b), and conversely every divisor of the gcd is a common divisor. So the set of positive common divisors is exactly the set of positive divisors of gcd(|a|,|b|) (with the usual care when both inputs are zero).

About the author

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)

9 people found this page helpful

C# Program to Check Triangular Number C# Program to find Composite Number

Find Common Divisors in C#

What you’ll learn

Overview

Two programs

Live preview

Interview polish

Prerequisites

What are common divisors?

GCD characterization

Intuition

Live preview

Algorithm

Naive scan

Gcd route

Euclidean gcd (core loop)

📜 Pseudocode

Naive scan up to min(a, b)

Explanation

Euclidean gcd, then divisors of g

Explanation

Optimization

❓ FAQ

🔄 Input / output examples

Edge cases and pitfalls

Negative inputs

One operand is zero

(0, 0)

int.MinValue

⏱️ Time and space complexity

Summary

🧩 Related topics

About the author

Naive scan up to `min(a, b)`

Euclidean gcd, then divisors of `g`

`(0, 0)`

`int.MinValue`