Definition
Shared factors
d is common if a % d == 0 and b % d == 0.
Find Common Divisors in Python
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 Python examples, edge cases, and complexity.
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
math.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.
python
# 24 and 36 → gcd = 12 → divisors 1, 2, 3, 4, 6, 12Inputs & Outputs
| Item | Type | Description |
|---|---|---|
a, b | int | Any integers (use absolute values for positive divisors). |
| Return / print | list[int] | Sorted positive common divisors (empty if both are 0). |
Minimal workflow
Pseudocode (naive)
function common_divisors_naive(a, b):
a = abs(a), b = abs(b)
limit = min(a, b) if min(a,b) > 0 else max(a,b)
for i from 1 to limit:
if a % i == 0 and b % i == 0:
output iMethod 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 and b % i == 0 |
| Absolute values | a, b = abs(a), abs(b) |
| Compute gcd | math.gcd(a, b) |
| Divisors of g | [i for i in range(1, g+1) 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 minEasy to explain; slow when both numbers are large
GCD linear
divisors of gUses 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 firstSay 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 Python 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.
python
def common_divisors_naive(a: int, b: int) -> list[int]:
a = abs(a)
b = abs(b)
if a == 0 and b == 0:
return []
limit = min(a, b) if min(a, b) > 0 else max(a, b)
ans = []
for i in range(1, limit + 1):
if a % i == 0 and b % i == 0:
ans.append(i)
return ans
print("Common divisors of 24 and 36 are:", common_divisors_naive(24, 36))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.
python
import math
def common_divisors_via_gcd(a: int, b: int) -> list[int]:
a = abs(a)
b = abs(b)
if a == 0 and b == 0:
return []
g = math.gcd(a, b)
return [i for i in range(1, g + 1) if g % i == 0]
print("Common divisors of -12 and 18 are:", common_divisors_via_gcd(-12, 18))How It Works
math.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.
python
import math
def common_divisors_sqrt(a: int, b: int) -> list[int]:
a = abs(a)
b = abs(b)
if a == 0 and b == 0:
return []
g = math.gcd(a, b)
small, large = [], []
i = 1
while i * i <= g:
if g % i == 0:
small.append(i)
other = g // i
if other != i:
large.append(other)
i += 1
return small + large[::-1]
print(common_divisors_sqrt(24, 36))
print(common_divisors_sqrt(7, 11))How It Works
Small factors go into small; matching large partners into large. Reversing large at the end yields ascending order without a full sort.
🧠 How the Algorithm Finds Them
1
Normalize
Take absolute values; reject or special-case (0, 0).
Guard
2
Find gcd
Compute g = gcd(a, b) with Euclidean algorithm / math.gcd.
Reduce
3
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. Built-in GCD
math.gcdkeeps the Euclidean step short 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 [] or raise — 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
absbefore scanning.2. Ignoring (0, 0)
There is no finite complete list of common divisors.
→ Return [] or raise 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) |
🎉 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.
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.
5
Core concepts 01
Rule
d divides both
Definition 02
Theorem
Divisors of gcd
Math 03
Signs
Use abs first
Guard 04
Speed
O(√g) listing
Code 05
Edge
(0,0) special
Analysis❓ Frequently Asked Questions
A positive integer d is a common divisor of a and b if d divides both with remainder 0.
For positive inputs, a common divisor cannot be greater than the smaller number.
Common divisors of a and b are exactly the divisors of gcd(|a|, |b|).
Use absolute values. Divisibility for positive divisors depends on magnitude.
Common divisors are the divisors of the nonzero number. If both are 0, there is no finite list.
Naive: O(min(|a|,|b|)). GCD + divisor listing: O(log min + g) with g = gcd, or faster with an O(sqrt(g)) divisor scan.
Yes for any pair that is not both zero — 1 divides every integer.
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.
About the author
9 people found this page helpful