snippetjavascriptTip

How can I calculate the greatest common divisor & least common multiple in JavaScript?

Submitted by: @import:30-seconds-of-code·Mar 2, 2026·

Viewed 0 times

leastjavascriptgreatesthowcommondivisormultiplecalculatethecan

Problem

The greatest common divisor (GCD), of two or more integers is the largest positive integer that divides each of the integers.
The Euclidean algorithm is an efficient method for computing the GCD of two numbers. This, in practice, means recursively applying the observation that gcd(a, b) = gcd(b, a % b) until b is zero. When b is zero, we have gcd(a, 0) = a.
<latex-expression>
</latex-expression>
The GCD of more than two numbers can be calculated by calculating the GCD of each pair of numbers. On top of the recursive function, we can use Array.prototype.reduce() to apply the operation to multiple numbers. The resulting value of a pair of numbers is then used as the first argument in the next step.

Solution

gcd(a, b) = \begin{cases}
\text{a} & \text{if } b = 0 \\
gcd(b, a \mod b) & \text{otherwise}
\end{cases}

<latex-expression>
</latex-expression>
The GCD of more than two numbers can be calculated by calculating the GCD of each pair of numbers. On top of the recursive function, we can use Array.prototype.reduce() to apply the operation to multiple numbers. The resulting value of a pair of numbers is then used as the first argument in the next step.
The least common multiple (LCM) of two numbers is the smallest positive integer that is perfectly divisible by the two given numbers.
The LCM of two numbers can be calculated by using the greatest common divisor (GCD) formula and the fact that lcm(x, y) = x * y / gcd(x, y).
<latex-expression>

Code Snippets

gcd(a, b) = \begin{cases}
\text{a} & \text{if } b = 0 \\
gcd(b, a \mod b) & \text{otherwise}
\end{cases}

const gcd = (a, b) => (!b ? a : gcd(b, a % b));

gcd(8, 36); // 4

const gcd = (a, b) => (!b ? a : gcd(b, a % b));
const gcdMultiple = (...arr) => [...arr].reduce((a, b) => gcd(a, b));

gcdMultiple(8, 36); // 4
gcdMultiple(...[12, 8, 32]); // 4

Context

From 30-seconds-of-code: gcd-lcm

Revisions (0)

No revisions yet.