Find Common Divisors in C

Q: What is a common divisor of two numbers?

A positive integer d is a common divisor of a and b if d divides both with remainder 0.

Q: Why can we scan only to min(a, b)?

For positive inputs, a common divisor cannot be greater than the smaller number.

Q: What about negative numbers?

Use absolute values. Divisibility for positive divisors depends on magnitude.

Q: What if one number is 0?

Common divisors are the divisors of the nonzero number. If both are 0, there is no finite list.

Q: What is the time complexity?

Naive: O(min(|a|,|b|)). GCD + divisor listing: O(log min + g) with g = gcd, or faster with an O(sqrt(g)) divisor scan.

Q: Is 1 always a common divisor?

Yes for any pair that is not both zero — 1 divides every integer.

Q: Should I list divisors in sorted order?

Usually yes for interviews. Collect pairs carefully when using the sqrt method, then sort if needed.

Beginner

⏱️ 10 min read

📚 Updated: Aug 2026

🎯 3 Code Examples

🚀 Live Preview

Number theory

Overview

What You’ll Learn

Common divisors are positive integers that divide both inputs exactly. This tutorial covers the gcd characterization, a live preview, algorithm steps, worked C examples, edge cases, and complexity.

Definition

Shared factors

d is common if a % d == 0 and b % d == 0.

GCD Link

Key theorem

Common divisors of a and b are exactly the divisors of gcd(|a|, |b|).

Naive Scan

Up to min

Try every i from 1 to min(|a|, |b|) and keep shared factors.

GCD Route

Euclidean gcd

Compute g, then list divisors of g only.

Live Preview

Try any pair

Enter two integers and list all positive common divisors.

Complexity

O / sqrt

Naive O(min); gcd + O(sqrt(g)) divisor scan is the interview upgrade.

Introduction

Common divisors are the positive integers that divide both a and b with remainder 0. Example: divisors of 12 are 1, 2, 3, 4, 6, 12 and of 18 are 1, 2, 3, 6, 9, 18 — shared list is 1, 2, 3, 6.

The elegant framing: if g = gcd(|a|, |b|), then the positive common divisors are exactly the divisors of g. That turns a two-number problem into a one-number divisor listing task.

Why it matters?

It connects remainder checks, Euclidean gcd, and divisor enumeration — core number-theory tools for interviews.

Key Highlights

Shared Factors

Both remainders must be zero.

GCD First

List divisors of gcd only.

Use abs

Signs do not change positive divisors.

Watch (0, 0)

No finite list of common divisors.

In short: find g = gcd(|a|, |b|), then list every positive divisor of g.

Foundation

📝 Problem & Approach

Given two integers, print all positive integers that divide both exactly.

// 24 and 36 → gcd = 12 → divisors 1, 2, 3, 4, 6, 12

Inputs & Outputs

Item	Type	Description
`a`, `b`	int	Any integers (use absolute values for positive divisors).
Return / print	int buffer + count	Sorted positive common divisors (empty if both are 0).

Minimal workflow

Pseudocode (naive)

function commonDivisorsNaive(a, b):
    a = abs(a), b = abs(b)
    limit = min(a,b) > 0 ? min(a,b) : max(a,b)
    for i from 1 to limit:
        if a % i == 0 and b % i == 0:
            output i

Method comparison

Method	Idea	Notes
Naive scan	Check every i up to min(\|a\|, \|b\|)	Clearest for beginners
GCD + linear divisors	List every divisor of g = gcd	O(g) after Euclidean step
GCD + sqrt divisors	Pair factors up to √g	Interview optimization

Cheat Sheet

⚡ Quick Reference

Goal	Pattern
Shared factor check	`a % i == 0 && b % i == 0`
Absolute values	`a = abs(a); b = abs(b);`
Compute gcd	`gcd(a, b)`
Divisors of g	`for (i = 1; i <= g; i++) if (g % i == 0)`
Classic pair	`24, 36 → 1, 2, 3, 4, 6, 12`
Both zero	Return empty / report no finite list

Compare

📋 Naive vs GCD Linear vs GCD Sqrt

Same common-divisor list — different speed and interview signaling.

Naive

scan to min

Easy to explain; slow when both numbers are large

GCD linear

divisors of g

Uses the theorem; loop length is g, not min(a,b)

GCD sqrt

O(√g)

Pair each i with g / i when i divides g

Interview tip

state gcd first

Say the characterization before writing loops

Context

When This Problem Shows Up

Reach for common-divisor drills when gcd and factor listing matter.

Interview warm-ups
Checks remainder logic and whether you know the gcd theorem.
Teaching Euclidean gcd
Gives a concrete reason to compute gcd beyond “largest shared factor.”
Gateway to LCM / fractions
Shared factors show up when simplifying ratios and grids.
Contest number theory
Often a sub-step inside larger gcd / divisor problems.
Not for listing all pairs of factors of a alone
This problem is specifically about factors shared by two numbers.

Key benefit: one short problem that teaches gcd theory, remainder loops, and divisor-listing optimizations together.

Interactive

🔮 Live Preview

Enter two integers and list all positive common divisors.

Hands-On

Examples Gallery

Three complete C programs — naive scan, gcd + linear divisors, and gcd + sqrt factor pairs. Click View Output to reveal sample console results.

📚 Getting Started

Direct scan — the clearest beginner approach.

Example 1 — Direct Scan up to min(a, b)

Take absolute values, then test every candidate up to the smaller magnitude.

#include <stdio.h>
#include <stdlib.h>

int commonDivisorsNaive(int a, int b, int out[], int cap) {
    int i;
    int count = 0;
    int limit;

    a = abs(a);
    b = abs(b);

    if (a == 0 && b == 0) {
        return 0;
    }

    limit = (a < b ? a : b);
    if (limit == 0) {
        limit = (a > b ? a : b);
    }

    for (i = 1; i <= limit; i++) {
        if (a % i == 0 && b % i == 0) {
            if (count < cap) {
                out[count++] = i;
            }
        }
    }
    return count;
}

int main(void) {
    int result[128];
    int n = commonDivisorsNaive(24, 36, result, 128);
    int i;

    printf("Common divisors of 24 and 36 are: [");
    for (i = 0; i < n; i++) {
        if (i) {
            printf(", ");
        }
        printf("%d", result[i]);
    }
    printf("]\n");
    return 0;
}

How It Works

After handling (0, 0), the loop upper bound is the smaller positive magnitude (or the nonzero value if one input is 0). Each i that divides both is appended.

⚡ GCD Characterization

Use the theorem: common divisors = divisors of gcd.

Example 2 — GCD First, Then Divisors of GCD

Cleaner mathematically and often faster when gcd is small.

#include <stdio.h>
#include <stdlib.h>

int gcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int commonDivisorsViaGcd(int a, int b, int out[], int cap) {
    int i;
    int count = 0;
    int g;

    a = abs(a);
    b = abs(b);

    if (a == 0 && b == 0) {
        return 0;
    }

    g = gcd(a, b);
    for (i = 1; i <= g; i++) {
        if (g % i == 0) {
            if (count < cap) {
                out[count++] = i;
            }
        }
    }
    return count;
}

int main(void) {
    int result[128];
    int n = commonDivisorsViaGcd(-12, 18, result, 128);
    int i;

    printf("Common divisors of -12 and 18 are: [");
    for (i = 0; i < n; i++) {
        if (i) {
            printf(", ");
        }
        printf("%d", result[i]);
    }
    printf("]\n");
    return 0;
}

How It Works

A Euclidean gcd runs in roughly O(log min). Then you only scan 1…g instead of 1…min(a, b). Negatives are normalized with abs first.

⚙️ Optimized Divisor Listing

Enumerate factors of g in O(√g) time.

Example 3 — GCD + Sqrt Factor Pairs

For each i ≤ √g that divides g, also collect g / i.

#include <stdio.h>
#include <stdlib.h>

int gcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int commonDivisorsSqrt(int a, int b, int out[], int cap) {
    int i;
    int g;
    int smallCount = 0;
    int large[128];
    int largeCount = 0;
    int count = 0;

    a = abs(a);
    b = abs(b);

    if (a == 0 && b == 0) {
        return 0;
    }

    g = gcd(a, b);
    for (i = 1; i * i <= g; i++) {
        if (g % i == 0) {
            if (smallCount < cap) {
                out[smallCount++] = i;
            }
            {
                int other = g / i;
                if (other != i && largeCount < 128) {
                    large[largeCount++] = other;
                }
            }
        }
    }

    /* append large partners in ascending order */
    count = smallCount;
    for (i = largeCount - 1; i >= 0; i--) {
        if (count < cap) {
            out[count++] = large[i];
        }
    }
    return count;
}

void printList(const int v[], int n) {
    int i;
    printf("[");
    for (i = 0; i < n; i++) {
        if (i) {
            printf(", ");
        }
        printf("%d", v[i]);
    }
    printf("]\n");
}

int main(void) {
    int buf[256];
    int n;

    n = commonDivisorsSqrt(24, 36, buf, 256);
    printList(buf, n);
    n = commonDivisorsSqrt(7, 11, buf, 256);
    printList(buf, n);
    return 0;
}

How It Works

Small factors go into small; matching large partners into large. appending large in reverse at the end yields ascending order without a full sort.

🧠 How the Algorithm Finds Them

Normalize

Take absolute values; reject or special-case (0, 0).

Guard

Find gcd

Compute g = gcd(a, b) with the Euclidean algorithm.

Reduce

List divisors of g

Linear scan 1…g, or collect factor pairs up to √g.

Enumerate

Common divisors

Return the sorted positive divisors of g — that is the full common list.

Trace

🔎 Worked Walkthrough — 24 and 36

Trace the gcd route. Euclidean steps, then divisors of g = 12.

Step	Action	Result
1	`gcd(36, 24)`	`36 % 24 = 12`
2	`gcd(24, 12)`	`24 % 12 = 0` → g = 12
3	Divisors of 12	`1, 2, 3, 4, 6, 12`

Final common divisors: 1, 2, 3, 4, 6, 12.

Use Cases

Where common-divisor listing shows up beyond the interview prompt.

1. Interview Warm-Ups

Tests remainder checks and gcd awareness.

Example: list common divisors of 24 and 36.

2. Teaching Number Theory

Makes the “divisors of gcd” theorem concrete.

Example: chalkboard 12 and 18.

3. Fraction Simplification

Shared factors are what cancel in a / b.

Example: reduce 24/36 by dividing by 12.

4. Grid / Tile Sizes

Common tile sizes that fit two dimensions exactly.

Example: tile a 24×36 board.

5. Contest Subroutines

Often a helper inside larger divisor / gcd problems.

Example: enumerate candidates dividing both n and m.

6. Complexity Practice

Compare O(min) vs O(log + √g) convincingly.

Example: “why gcd first?”

Pro Tip: say the gcd characterization out loud before coding — interviewers often score that explanation as highly as the loop.

Advantages

Why the gcd framing works so well.

1. Math Maps Cleanly
Common divisors = divisors of gcd — one sentence that drives the code.
2. Euclidean GCD
A short while (b != 0) loop keeps the gcd step clear and correct.
3. Clear Optimizations
Sqrt divisor listing is a natural upgrade from the linear scan.
4. Easy Edge Cases
Signs, zeros, and coprime pairs give structured follow-ups.

Pro Tip: if asked for only the count of common divisors, still compute gcd first — then count divisors of g.

Usage Tips

Small habits that keep common-divisor solutions interview-ready.

1. State the GCD Theorem First
Explain before coding — it shows number-theory fluency.
2. Always Use abs
Positive divisors depend on magnitude, not sign.
3. Handle (0, 0) Explicitly
Return an empty list or throw — document the choice.
4. Spot-Check 24 and 36
Expect 1, 2, 3, 4, 6, 12 as a golden test.
5. Prefer Sqrt Listing for Large g
Mention O(√g) when gcd can be huge.

Pro Tip: for one input 0, common divisors are just the divisors of the nonzero number — gcd already encodes that.

Common Pitfalls

Mistakes that commonly break common-divisor solutions.

1. Forgetting abs
Negative inputs can confuse homemade loops.
→ Normalize with abs before scanning.
2. Ignoring (0, 0)
There is no finite complete list of common divisors.
→ Return an empty list or throw with a clear message.
3. Scanning Past min Unnecessarily
A common divisor cannot exceed the smaller positive magnitude.
→ Cap naive loops at min, or better — use gcd.
4. Duplicate Factors in Sqrt Method
When i * i == g, appending both sides twice is wrong.
→ Only add the pair partner when other != i.
5. Confusing GCD with the Full List
gcd is the largest common divisor, not the only one.
→ Still enumerate all divisors of g when asked for common divisors.

Edge Cases

Check these inputs before calling the solution done.

Both zero

(0, 0)

No finite list to display.

Negative values

Use abs

Use absolute values before gcd/divisor checks.

One zero

(0, n)

Common divisors are the divisors of |n|.

Coprime

gcd = 1

Only common divisor is 1 (e.g. 7 and 11).

Performance

Huge gcd

Listing all divisors can be large output — prefer O(√g).

Equal inputs

a == b

Common divisors are simply all positive divisors of |a|.

Math

⚖️ Facts Worth Knowing

Handy follow-ups interviewers sometimes ask.

Characterization. Positive common divisors of a and b = positive divisors of gcd(|a|, |b|).
Largest is gcd. The maximum common divisor is exactly gcd(a, b).
LCM link. For positive a, b: lcm(a, b) = a / gcd(a, b) * b.
Always include 1. Unless both inputs are 0, 1 is always a common divisor.

Drill

🎯 Practice Problems

Try these variations to lock in the pattern.

1. Verify classics

24, 36 → 1,2,3,4,6,12
12, 18 → 1,2,3,6
7, 11 → 1

2. Signs and zeros

Handle -12 and 18
Document (0, 0) behavior

3. Implement both styles

Naive and gcd + sqrt
Assert identical sorted lists

4. Count only

Return the count of common divisors
Still use gcd first

Important

Notes

Core idea: common divisors are shared exact factors — equivalently, divisors of gcd.
Use absolute values; treat (0, 0) as a special case.
In interviews, state the gcd relation before writing loops.
Prefer O(log + √g) over O(min) when magnitudes can be large.

Quick Takeaway: compute g = gcd(|a|, |b|), then list every positive divisor of g.

Analysis

⏱️ Time and Space Complexity

Program	Time	Extra space
Naive scan	`O(min(\|a\|, \|b\|))`	`O(1)` (+ output)
GCD + linear divisor scan	`O(log min + g)`	`O(1)` (+ output)
GCD + sqrt divisor pairs	`O(log min + √g)`	`O(1)` (+ output)

Wrap Up

🎉 Conclusion

Common divisors are shared exact factors — and equivalently, the positive divisors of gcd(|a|, |b|). Start with a naive scan if needed, then upgrade to gcd + divisor listing (linear or sqrt).

Practice the three examples above, then continue to prime numbers for another classic number-theory warm-up.

Always use abs, handle (0, 0), state the gcd theorem, and prefer O(√g) divisor listing when g can be large.

View Examples Gallery Continue to Prime Number

Pro Tips

💡 Best Practices

✅ Do

State “divisors of gcd” first
Normalize with abs
Handle (0, 0) explicitly
Test 24/36 and coprime pairs
Offer O(√g) as an upgrade

❌ Don’t

Forget signs / abs
Treat gcd as the only answer when a list is asked
Scan past min without reason
Duplicate perfect-square factors
Skip empty-list policy for (0, 0)

Summary

Key Takeaways

Knowledge Unlocked

Five things to remember about common divisors

List shared factors the interview-friendly way.

Core concepts

% 01

Rule

d divides both

Definition

g 02

Theorem

Divisors of gcd

Math

| 03

Signs

Use abs first

Guard

√ 04

Speed

O(√g) listing

Code

0 05

Edge

(0,0) special

Analysis

❓ Frequently Asked Questions

What is a common divisor of two numbers?

A positive integer d is a common divisor of a and b if d divides both with remainder 0.

Why can we scan only to min(a, b)?

For positive inputs, a common divisor cannot be greater than the smaller number.

How does gcd help here?

Common divisors of a and b are exactly the divisors of gcd(|a|, |b|).

What about negative numbers?

Use absolute values. Divisibility for positive divisors depends on magnitude.

What if one number is 0?

Common divisors are the divisors of the nonzero number. If both are 0, there is no finite list.

What is the time complexity?

Naive: O(min(|a|,|b|)). GCD + divisor listing: O(log min + g) with g = gcd, or faster with an O(sqrt(g)) divisor scan.

Is 1 always a common divisor?

Yes for any pair that is not both zero — 1 divides every integer.

Should I list divisors in sorted order?

Usually yes for interviews. Collect pairs carefully when using the sqrt method, then sort if needed.

Did you Know? 🔊

Every common divisor of a and b divides gcd(a, b), and every divisor of gcd(a, b) is a common divisor.

Continue to Prime Number

Learn how to check whether a number is prime with trial division and sqrt optimizations.

Prime number tutorial →

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 Convert Binary to Decimal C Program to Check Prime Number

Find Common Divisors in C

What You’ll Learn

Definition

GCD Link

Naive Scan

GCD Route

Live Preview

Complexity

Introduction

Why it matters?

Shared Factors

GCD First

Use abs

Watch (0, 0)

📝 Problem & Approach

Inputs & Outputs

Minimal workflow

Method comparison

⚡ Quick Reference

📋 Naive vs GCD Linear vs GCD Sqrt

When This Problem Shows Up

Interview warm-ups

Teaching Euclidean gcd

Gateway to LCM / fractions

Contest number theory

Not for listing all pairs of factors of a alone

🔮 Live Preview

Examples Gallery

📚 Getting Started

Example 1 — Direct Scan up to min(a, b)

How It Works

⚡ GCD Characterization

Example 2 — GCD First, Then Divisors of GCD

How It Works

⚙️ Optimized Divisor Listing

Example 3 — GCD + Sqrt Factor Pairs

How It Works

🧠 How the Algorithm Finds Them

Normalize

Find gcd

List divisors of g

Common divisors

🔎 Worked Walkthrough — 24 and 36

Use Cases

1. Interview Warm-Ups

2. Teaching Number Theory

3. Fraction Simplification

4. Grid / Tile Sizes

5. Contest Subroutines

6. Complexity Practice

Advantages

1. Math Maps Cleanly

2. Euclidean GCD

3. Clear Optimizations

4. Easy Edge Cases

Usage Tips

1. State the GCD Theorem First

2. Always Use abs

3. Handle (0, 0) Explicitly

4. Spot-Check 24 and 36

5. Prefer Sqrt Listing for Large g

Common Pitfalls

1. Forgetting abs

2. Ignoring (0, 0)

3. Scanning Past min Unnecessarily

4. Duplicate Factors in Sqrt Method

5. Confusing GCD with the Full List

Edge Cases

(0, 0)

Use abs

(0, n)

gcd = 1

Huge gcd

a == b

⚖️ Facts Worth Knowing

🎯 Practice Problems

1. Verify classics

2. Signs and zeros

3. Implement both styles

4. Count only