A common divisor of two integers is a positive integer that divides both of them with no remainder.
Remember
d is a common divisor of a and b
↔ a % d == 0 and b % d == 0
Key fact: common divisors of a, b
= all positive divisors of gcd(|a|, |b|)
Example: 24 and 36
gcd = 12
common divisors: 1, 2, 3, 4, 6, 12
a
b
gcd
Common divisors
24
36
12
1, 2, 3, 4, 6, 12
-12
18
6
1, 2, 3, 6
7
11
1
1
0
10
10
1, 2, 5, 10
Approach
How to Find Common Divisors in C++
Scan candidates, or compute gcd first and list its divisors.
Take absolute values (positive divisors).
Reject both-zero (no finite list).
Either scan 1…min, or compute g = gcd and list divisors of g.
Return the sorted list of matches.
Method
Idea
Time
Best for
Naive scan
Test 1…min(|a|,|b|)
O(min)
Interviews, clarity
Via gcd
Divisors of gcd(a,b)
O(log + g)
Cleaner math
Gcd + √g
Factor pairs of gcd
O(log + √g)
Faster listing
Pseudocode
Pseudocode
function CommonDivisors(a, b):
a = abs(a); b = abs(b)
if a == 0 and b == 0:
return [] // undefined / infinite
g = gcd(a, b)
result = []
for i from 1 to g:
if g mod i == 0:
result.append(i)
return result
Reference
Cheat Sheet
Keep these facts handy while writing the program.
Topic
Detail
Test
a % d == 0 && b % d == 0
Theorem
Common divisors = divisors of gcd
Classic
24, 36 → 1, 2, 3, 4, 6, 12
Always
1 is a common divisor (unless both 0)
Both 0
No finite list — return empty / error
Try it
Live Preview
Enter two integers to see gcd and every common divisor.
Any integers (including negatives). Tap a chip or type a pair.
Result
a = 24, b = 36
gcd = 12
Common divisors: 1, 2, 3, 4, 6, 12
Trace
Worked Walkthrough — 24 and 36
Find gcd, then list every positive divisor of that gcd.
Calculation
gcd(24, 36):
36 = 24×1 + 12
24 = 12×2 + 0
gcd = 12
Divisors of 12:
1, 2, 3, 4, 6, 12
Each divides both 24 and 36
→ common divisors = 1, 2, 3, 4, 6, 12
Code
C++ Programs
Start with a direct scan. Then use gcd, and finish with an O(√g) factor-pair listing.
Example 1 — Direct Scan up to min(a, b)
Take absolute values, then test every candidate up to the smaller magnitude.
C++
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
std::vector<int> commonDivisorsNaive(int a, int b) {
a = std::abs(a);
b = std::abs(b);
std::vector<int> ans;
if (a == 0 && b == 0) {
return ans;
}
int limit = std::min(a, b) > 0 ? std::min(a, b) : std::max(a, b);
for (int i = 1; i <= limit; i++) {
if (a % i == 0 && b % i == 0) {
ans.push_back(i);
}
}
return ans;
}
int main() {
std::vector<int> result = commonDivisorsNaive(24, 36);
std::cout << "Common divisors of 24 and 36 are: [";
for (size_t i = 0; i < result.size(); i++) {
if (i) std::cout << ", ";
std::cout << result[i];
}
std::cout << "]\n";
return 0;
}
Output
Common divisors of 24 and 36 are: [1, 2, 3, 4, 6, 12]
How It Works
Normalize with std::abs; return empty for (0, 0).
Upper bound is the smaller positive magnitude (or the nonzero value if one is 0).
Append every i that divides both.
Results are already ascending.
Clearest interview version — easy to explain.
Example 2 — GCD First, Then Divisors of GCD
Cleaner mathematically and often faster when gcd is small.
C++
#include <iostream>
#include <vector>
#include <cstdlib>
int gcd(int a, int b) {
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return a;
}
std::vector<int> commonDivisorsViaGcd(int a, int b) {
a = std::abs(a);
b = std::abs(b);
std::vector<int> ans;
if (a == 0 && b == 0) {
return ans;
}
int g = gcd(a, b);
for (int i = 1; i <= g; i++) {
if (g % i == 0) {
ans.push_back(i);
}
}
return ans;
}
int main() {
std::vector<int> result = commonDivisorsViaGcd(-12, 18);
std::cout << "Common divisors of -12 and 18 are: [";
for (size_t i = 0; i < result.size(); i++) {
if (i) std::cout << ", ";
std::cout << result[i];
}
std::cout << "]\n";
return 0;
}
Output
Common divisors of -12 and 18 are: [1, 2, 3, 6]
How It Works
Euclidean gcd runs in roughly O(log min).
Scan only 1…g instead of 1…min(a, b).
Every divisor of g is a common divisor of a and b.
Negatives are handled by std::abs first.
For -12 and 18, gcd is 6 → 1, 2, 3, 6.
Example 3 — GCD + Sqrt Factor Pairs
For each i ≤ √g that divides g, also collect g / i.
C++
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
int gcd(int a, int b) {
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return a;
}
std::vector<int> commonDivisorsSqrt(int a, int b) {
a = std::abs(a);
b = std::abs(b);
std::vector<int> small;
std::vector<int> large;
if (a == 0 && b == 0) {
return small;
}
int g = gcd(a, b);
for (int i = 1; i * i <= g; i++) {
if (g % i == 0) {
small.push_back(i);
int other = g / i;
if (other != i) {
large.push_back(other);
}
}
}
std::reverse(large.begin(), large.end());
small.insert(small.end(), large.begin(), large.end());
return small;
}
void printList(const std::vector<int>& v) {
std::cout << "[";
for (size_t i = 0; i < v.size(); i++) {
if (i) std::cout << ", ";
std::cout << v[i];
}
std::cout << "]\n";
}
int main() {
printList(commonDivisorsSqrt(24, 36));
printList(commonDivisorsSqrt(7, 11));
return 0;
}
Output
[1, 2, 3, 4, 6, 12]
[1]
How It Works
Compute g = gcd(a, b) as before.
Loop while i * i <= g; when i divides g, store i and g/i.
Small factors go into small; large partners into large.
Reverse large and append for ascending order without a full sort.
Coprime pair 7, 11 yields only [1].
Edge Cases & Pitfalls
Check these before calling the solution done.
Both 0
No finite list
Every positive integer divides 0. Return empty or an explicit error.
One 0
Divisors of the other
Common divisors of 0 and n are the positive divisors of |n|.
Negatives
Use absolute values
Positive common divisors ignore sign — call std::abs first.
Order
Prefer sorted output
With the sqrt method, reverse the large partners so the list stays ascending.
Analysis
Time and Space Complexity
Program
Time
Extra space
Naive scan
O(min(|a|,|b|))
O(k) for k matches
Via gcd (linear list)
O(log min + g)
O(k)
Gcd + √g pairs
O(log min + √g)
O(k)
Here g = gcd(|a|,|b|) and k is the number of common divisors.
Remember
Key Takeaways
Definition: positive d that divides both a and b.
Theorem: common divisors = divisors of gcd.
Classic: 24 & 36 → 1, 2, 3, 4, 6, 12.
Speed: list factors of g in O(√g) when g is large.
One line: find gcd, then list every positive divisor of that gcd.
Frequently Asked Questions
A positive integer d is a common divisor of a and b if d divides both with remainder 0.
The common divisors of a and b are exactly the divisors of gcd(|a|, |b|).
Use absolute values. Positive divisors depend 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 then divisors of g: O(log min + g), or O(log min + √g) with a sqrt scan.
