12 & 181,2,3,6
Find Common Divisors in PHP
What you’ll learn
- Common divisors meaning and gcd relation.
- Naive scan and gcd-first methods.
- Handling signs, zeros, and complexity.
Overview
List all positive integers that divide both numbers.
Prerequisites
Modulo operator, loops, and integer basics.
%,for, andwhile.- Absolute value and gcd concept.
What are common divisors?
A number is common divisor of a and b if both a % d == 0 and b % d == 0.
GCD characterization
Common divisors of a and b are exactly divisors of gcd(|a|,|b|).
Intuition
24 & 361,2,3,4,6,12
Live preview
Algorithm
Goal: list positive common divisors.
1
Naive: loop i from 1 to min(abs(a),abs(b)), test both modulo zero.
2
Gcd route: compute g, then list divisors of g.
📜 Pseudocode
Pseudocode
g = gcd(abs(a), abs(b))
for i in 1..g:
if g % i == 0: print i1
Naive scan up to min(a,b)
php
<?php
function findCommonDivisorsNaive(int $a, int $b): array
{
$x = abs($a); $y = abs($b);
if ($x === 0 && $y === 0) return [];
$limit = ($x === 0) ? $y : (($y === 0) ? $x : min($x, $y));
$ans = [];
for ($i = 1; $i <= $limit; $i++) {
if ($a % $i === 0 && $b % $i === 0) $ans[] = $i;
}
return $ans;
}
echo implode(" ", findCommonDivisorsNaive(24, 36));
?>2
GCD first, then divisors of g
php
<?php
function gcdNonNeg(int $a, int $b): int
{
$a = abs($a); $b = abs($b);
while ($b !== 0) { $t = $a % $b; $a = $b; $b = $t; }
return $a;
}
function commonDivisorsViaGcd(int $a, int $b): array
{
if ($a === 0 && $b === 0) return [];
$g = gcdNonNeg($a, $b);
$ans = [];
for ($i = 1; $i <= $g; $i++) if ($g % $i === 0) $ans[] = $i;
return $ans;
}
echo implode(" ", commonDivisorsViaGcd(24, 36));
?>Optimization
Use gcd first to reduce search space.
For large g, iterate to sqrt(g) and add divisor pairs.
❓ FAQ
A positive integer that divides both input numbers exactly.
Every common divisor divides gcd(a,b), and every divisor of gcd(a,b) is common to both.
Use absolute values before computing divisors.
That case is special because every nonzero integer divides 0.
Naive scan is O(min(|a|,|b|)); gcd with divisor listing is O(log min + g) in simple form.
🔄 Input / output examples
| a | b | Common divisors |
|---|---|---|
24 | 36 | 1 2 3 4 6 12 |
12 | 18 | 1 2 3 6 |
Edge cases and pitfalls
Signs
Negative inputs
Use absolute values for divisor listing.
Zero
One or both zero
Handle (0,0) as special case.
⏱️ Time and space complexity
| Approach | Time | Extra space |
|---|---|---|
| Naive scan | O(min(|a|,|b|)) | O(1) |
| GCD + divisors | O(log min + g) | O(1) |
Summary
- Common divisors come from gcd.
- Naive and gcd-based solutions are both useful.
- Always handle zero/sign cases carefully.
Did you know?
Common divisors of two numbers are exactly the divisors of their gcd (except the special case of 0 and 0).
About the author
8 people found this page helpful