How to find the greatest common divisor in JavaScript
Łukasz Holeczek
Follow Łukasz Holeczek on GitHub
Connect with Łukasz Holeczek on LinkedIn
Follow Łukasz Holeczek on X (Twitter)
Finding the greatest common divisor (GCD) is crucial for fraction simplification, cryptographic algorithms, mathematical computations, and implementing features like ratio calculations or modular arithmetic in JavaScript applications. With over 25 years of experience in software development and as the creator of CoreUI, I’ve implemented GCD calculations in components like mathematical tools, fraction reducers, and algorithm demonstrations where efficient number theory operations are essential for accurate computations. From my extensive expertise, the most efficient approach is the Euclidean algorithm using either recursive or iterative implementation. This ancient algorithm provides optimal performance with O(log min(a,b)) time complexity and handles all positive integer inputs reliably.
Use the Euclidean algorithm with modulo operation to find the GCD efficiently.
const gcd = (a, b) => {
while (b !== 0) {
const temp = b
b = a % b
a = temp
}
return a
}
// Usage: gcd(48, 18) returns 6, gcd(17, 13) returns 1
The Euclidean algorithm repeatedly applies the principle that GCD(a, b) = GCD(b, a mod b) until one number becomes zero. In the example, GCD(48, 18): first iteration sets a=18, b=48%18=12; second iteration sets a=12, b=18%12=6; third iteration sets a=6, b=12%6=0. When b becomes 0, a contains the GCD (6). The algorithm works because the remainder operation preserves the greatest common divisor while reducing the problem size. This iterative version avoids stack overflow issues that could occur with recursive implementations for very large numbers.
Best Practice Note:
This is the same approach we use in CoreUI components for mathematical utilities, fraction operations, and algorithm implementations across our component library.
Alternative recursive version: const gcd = (a, b) => b === 0 ? a : gcd(b, a % b). Always use absolute values for negative inputs: Math.abs(a) and Math.abs(b). The algorithm works optimally when a ≥ b, but handles any order correctly. Consider memoization for repeated calculations with the same inputs.
