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

## Greatest common divisor

The greatest common divisor (**GCD**), of two or more integers is the largest positive integer that divides each of the integers.

### The Euclidean algorithm

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`

.

const gcd = (a, b) => (!b ? a : gcd(b, a % b)); gcd(8, 36); // 4

### Greatest common divisor of more than two numbers

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.

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

## Least common multiple

The least common multiple (**LCM**) of two numbers is the smallest positive integer that is perfectly divisible by the two given numbers.

### Least common multiple of two 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)`

.

const gcd = (a, b) => (!b ? a : gcd(b, a % b)); const lcm = (x, y) => (x * y) / gcd(x, y); lcm(12, 7); // 84

### Least common multiple of more than two numbers

Similarly to the GCD, the LCM of more than two numbers can be calculated with the help of `Array.prototype.reduce()`

. Start by calculating the LCM of the **first two numbers**, then keep applying the operation to the result and the next number until all numbers have been iterated over.

const gcd = (a, b) => (!b ? a : gcd(b, a % b)); const lcm = (x, y) => (x * y) / gcd(x, y); const lcmMultiple = (...arr) => [...arr].reduce((a, b) => lcm(a, b)); lcmMultiple(12, 7); // 84 lcmMultiple(...[1, 3, 4, 5]); // 60