# 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```

## More like this

• Collection · 25 snippets

### JavaScript Algorithms

Learn a handful of popular algorithms, implemented in JavaScript ES6.

• JavaScript ·

### How can I specify the base for a logarithm in JavaScript?

Calculate the logarithm of a number or check if a number is a power of a specific base.

• JavaScript ·

### Calculate the Euclidean distance in JavaScript

Use JavaScript's `Math.hypot()` to calculate the Euclidean distance between two points.

• JavaScript ·

### How can I convert between hexadecimal, RGB, HSL and HSB color formats in JavaScript?

Learn how to easily convert between the various color formats, using JavaScript and a few simple formulas.

Start typing a keyphrase to see matching snippets.