30秒学会 JavaScript 片段 · 2022年9月17日

30秒学会 JavaScript 片段 – 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

翻译自:https://www.30secondsofcode.org/js/s/gcd-lcm