12 & 18 gcd 6
- Common
1, 2, 3, 6
Find Common Divisors in Java
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 ofg. - A small 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 magnitude; a tighter characterization prints divisors of g = gcd(|a|,|b|).
Two programs
Double test each i against both inputs, then Euclidean gcd plus divisor scan of g.
Live preview
Enter two integers and see common divisors computed in the browser (same math as the samples).
Interview polish
State the gcd characterization, handle (0,0), and mention O(√g) divisor enumeration when g can be huge.
Prerequisites
Integer division, remainder (%), for loops, and the idea that d divides n when n % d == 0.
public static void main(String[] args), integer arithmetic, and printing withSystem.out.println.- Optional: Java’s
Math.absand understanding how the Euclidean gcd loop works.
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 intersection 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 36gcd(24, 36) = 12. Divisors of 12 are 1, 2, 3, 4, 6, 12—exactly the common divisors printed in the sample output.
Intuition
24 & 36 gcd 12
- Common
1, 2, 3, 4, 6, 12
Takeaway: common divisors are “shared building blocks” of both numbers; the gcd is the largest of them.
Live preview
Two integers (JavaScript safe range). Uses absolute values, Euclidean gcd, then lists positive divisors of the gcd. (0, 0) is flagged as ambiguous.
Algorithm
Goal: print all positive integers d such that a % d == 0 and b % d == 0.
Naive scan
Let m = min(|a|,|b|) (adjust if one argument is zero). For i from 1 to m, if a % i == 0 and b % i == 0, print i.
Gcd route
Compute g = gcd(|a|,|b|). For each i from 1 to g, if g % i == 0, print i. Same set of outputs; often fewer iterations when g is much smaller than min(|a|,|b|).
Euclidean gcd (core loop)
While b != 0: replace (a, b) with (b, a % b). The last nonzero a is the gcd of the original pair (up to sign).
📜 Pseudocode
Pseudocode (naive)
function printCommonDivisorsNaive(a, b):
m ← min(|a|, |b|) // handle a = 0 or b = 0 separately if needed
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 i1Naive scan up to
Naive scan up to min(a, b)
Matches the classic teaching flow: loop from 1 to the smaller of the two inputs and print when both remainders are zero. Assumes nonnegative inputs as in the original walkthrough (24 and 36).
java
public class Main {
static void findCommonDivisors(int num1, int num2) {
System.out.print("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) {
System.out.print(i + " ");
}
}
System.out.println();
}
public static void main(String[] args) {
int number1 = 24;
int number2 = 36;
findCommonDivisors(number1, number2);
}
}Explanation
Any common divisor cannot exceed min(num1, num2) when both are positive, so the loop upper bound is safe.
if (num1 % i == 0 && num2 % i == 0)Divisibility test. Both must agree on the same i.
2Euclidean gcd, then divisors of
Euclidean gcd, then divisors of g
Uses Math.abs so negative inputs follow the usual “positive divisor” convention. Treats (0, 0) explicitly because every nonzero integer divides both zeros.
java
public class Main {
static int gcdNonNeg(int a, int b) {
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return a;
}
static void printDivisorsAscending(int g) {
for (int i = 1; i <= g; i++) {
if (g % i == 0) {
System.out.print(i + " ");
}
}
}
static void findCommonDivisorsViaGcd(int num1, int num2) {
int a = Math.abs(num1);
int b = Math.abs(num2);
System.out.print("Common divisors of " + num1 + " and " + num2 + " are: ");
if (a == 0 && b == 0) {
System.out.println("(undefined: every nonzero d divides 0)");
return;
}
int g = gcdNonNeg(a, b);
printDivisorsAscending(g);
System.out.println();
}
public static void main(String[] args) {
findCommonDivisorsViaGcd(24, 36);
findCommonDivisorsViaGcd(-12, 18);
}
}Explanation
Divisors of g are exactly the positive common divisors of a and b once signs are stripped.
int g = gcdNonNeg(a, b);Euclidean gcd. Logarithmic number of iterations in typical bounds on |a|+|b|.
printDivisorsAscending(g);List D(g). For huge g, switch to an O(√g) pair scan in production code.
Optimization
Divisors of g. Enumerate i up to √g: whenever g % i == 0, output i and g / i (careful when i == g / i). Sorted order needs a small buffer or two passes.
Library gcd. In modern Java you can use BigInteger.gcd for big numbers; for int and long you usually write a short Euclidean helper as above.
Interview: state the gcd characterization before coding; mention (0,0) and sign conventions.
❓ FAQ
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.
Any integer larger than both |a| and |b| cannot divide the smaller nonzero magnitude, and a common divisor cannot exceed min(|a|,|b|) unless one number is 0. For two positive numbers, every common divisor is at most the smaller number.
The positive common divisors of a and b are exactly the positive divisors of g = gcd(|a|,|b|). You can implement Euclidean gcd yourself or use helper methods; once you know g, you only test divisors of g, not both original numbers.
Divisibility depends on magnitude: d divides n if and only if d divides |n| for nonzero d. Use absolute values (or careful modulus rules) so the logic matches the positive-divisor convention.
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.
Naive: O(min(|a|,|b|)) trials. Euclidean gcd is O(log min(|a|,|b|)) per step count; listing divisors of g is O(g) in the simple loop, or O(√g) if you enumerate divisor pairs.
🔄 Input / output examples
Replace number1 and number2 in Example 1, or extend main in Example 2 with more test pairs.
| 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 (Example 2 path) |
Edge cases and pitfalls
The naive loop assumes nonnegative inputs; signs, zeros, and Integer.MIN_VALUE with Math.abs need an explicit policy.
SignNegative
Negative num1 or num2
Example 1 uses num1 < num2 for the bound; for negative values the bound and % behavior need a redesign. Prefer absolute values (Example 2) or document “nonnegative only.”
Zero
One operand is zero
gcd(|a|,0) = |a|. The common divisors are the divisors of the nonzero magnitude. Example 1’s upper bound becomes 0 if you take min literally—handle that case.
Both zero
(0, 0)
Every nonzero d divides both; there is no finite “list all” answer. Return a message or an error code.
Cost
Huge gcd
Printing every divisor of a highly composite large g can be enormous output—not a complexity win if you only needed gcd or the count.
⏱️ Time and space complexity
| Approach | Time | Extra space |
|---|---|---|
Naive scan to min(|a|,|b|) | 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 itself; only a handful of integer locals are needed.
Summary
- Math: positive common divisors of
aandbare the positive divisors ofgcd(|a|,|b|)(except the pathological(0,0)case). - Code: naive double
%check, or gcd then list divisors ofg. - Watch-outs: nonnegative assumption in the simple loop,
(0,0),Integer.MIN_VALUEwithMath.abs, and output size whenghas many divisors.
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
8 people found this page helpful