12 & 18 gcd 6
- Common
1, 2, 3, 6
Find Common Divisors in JavaScript
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 scripts
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.
console.log,Math.abs, andNumber.isIntegerfor validating inputs in your own runners.- Optional: binary to decimal for another radix-flavored interview topic.
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 multiset 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 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).
JavaScript
function findCommonDivisors(num1, num2) {
const parts = [];
const limit = num1 < num2 ? num1 : num2;
for (let i = 1; i <= limit; i++) {
if (num1 % i === 0 && num2 % i === 0) {
parts.push(String(i));
}
}
console.log(
"Common divisors of " + num1 + " and " + num2 + " are: " + parts.join(" ")
);
}
const number1 = 24;
const 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.
JavaScript
function gcdNonneg(a, b) {
while (b !== 0) {
const t = a % b;
a = b;
b = t;
}
return a;
}
function findCommonDivisorsViaGcd(num1, num2) {
const a = Math.abs(num1);
const b = Math.abs(num2);
let line = "Common divisors of " + num1 + " and " + num2 + " are: ";
if (a === 0 && b === 0) {
console.log(line + "(undefined: every nonzero d divides 0)");
return;
}
const g = gcdNonneg(a, b);
const parts = [];
for (let i = 1; i <= g; i++) {
if (g % i === 0) {
parts.push(String(i));
}
}
console.log(line + parts.join(" "));
}
findCommonDivisorsViaGcd(24, 36);
findCommonDivisorsViaGcd(-12, 18);Explanation
Divisors of g are exactly the positive common divisors of a and b once signs are stripped.
const g = gcdNonneg(a, b);Euclidean gcd. Logarithmic number of iterations in typical bounds on |a|+|b|.
for (let i = 1; i <= g; i++)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, collect i and g / i (careful when i === g / i). Sorted output may need a buffer or two passes.
Big integers. For values outside Number.MAX_SAFE_INTEGER, implement the same loops with BigInt and % on BigInt operands.
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|). Compute g with the Euclidean algorithm, then list divisors of g—often fewer iterations than testing every i against both original numbers.
Divisibility depends on magnitude: d divides n if and only if d divides |n| for nonzero d. Use Math.abs (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 add more findCommonDivisorsViaGcd(…) calls in Example 2.
| 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 values outside the safe integer range 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), safe-integer range, 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