12 and 181,2,3,6
Find Common Divisors in Python
What you’ll learn
- What common divisors are and how they connect to gcd(a, b).
- A direct scan approach and a gcd-first approach.
- How to handle zero, negative values, and interview complexity questions.
Overview
Given two integers, print all positive integers that divide both exactly. A key fact is: common divisors of a and b are divisors of gcd(|a|, |b|).
Prerequisites
Remainder operator (%), loops, and absolute value.
- Python functions and loops.
- Optional:
math.gcdfrom Python standard library.
What are common divisors?
A positive integer d is a common divisor of a and b if both a % d == 0 and b % d == 0.
Example: divisors of 12 are 1,2,3,4,6,12 and divisors of 18 are 1,2,3,6,9,18. Common divisors are 1,2,3,6.
GCD characterization
If g = gcd(|a|, |b|), then divisors of g are exactly the positive common divisors of a and b.
Intuition
24 and 361,2,3,4,6,12
Live preview
Enter two integers and list all positive common divisors.
Algorithm
Naive scan
Try each i from 1 to min(abs(a), abs(b)).
GCD route
Find g = gcd(abs(a), abs(b)) and list divisors of g.
📜 Pseudocode
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 i1
Direct scan up to min(a, b)
Simple and easy to understand for beginners.
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))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))Optimization
Use gcd. Compute gcd first and factor only gcd.
Large values. Divisor listing can still be large if gcd has many divisors.
Interview tip: state the gcd relation before coding.
❓ FAQ
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.
🔄 Input / output examples
| a | b | Common divisors |
|---|---|---|
24 | 36 | 1,2,3,4,6,12 |
12 | 18 | 1,2,3,6 |
7 | 11 | 1 |
Edge cases and pitfalls
Both zero
(0,0)
No finite list to display.
Negative values
Use abs
Use absolute values before gcd/divisor checks.
Performance
Huge gcd
Listing all divisors can be large output.
⏱️ Time and space complexity
| Approach | Time | Extra space |
|---|---|---|
| Naive scan | O(min(|a|,|b|)) | O(1) |
| GCD + divisor scan | O(log min + g) | O(1) |
Summary
- Core idea: common divisors are shared exact factors.
- Best framing: divisors of gcd(a,b).
- Careful with: signs and (0,0).
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.
About the author
8 people found this page helpful