Euclidean Algorithm

In mathematics, the Euclidean algorithm, or Euclid’s algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder.

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, `21` is the GCD of `252` and `105` (as `252 = 21 × 12` and `105 = 21 × 5`), and the same number `21` is also the GCD of `105` and `252 − 105 = 147`. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers.

By reversing the steps, the GCD can be expressed as a sum of the two original numbers each multiplied by a positive or negative integer, e.g., `21 = 5 × 105 + (−2) × 252`. The fact that the GCD can always be expressed in this way is known as Bézout's identity.

A `24-by-60` rectangle is covered with ten `12-by-12` square tiles, where `12` is the GCD of `24` and `60`. More generally, an `a-by-b` rectangle can be covered with square tiles of side-length `c` only if `c` is a common divisor of `a` and `b`.

Subtraction-based animation of the Euclidean algorithm. The initial rectangle has dimensions `a = 1071` and `b = 462`. Squares of size `462×462` are placed within it leaving a `462×147` rectangle. This rectangle is tiled with `147×147` squares until a `21×147` rectangle is left, which in turn is tiled with `21×21` squares, leaving no uncovered area. The smallest square size, `21`, is the GCD of `1071` and `462`.

`/** * Recursive version of Euclidean Algorithm of finding greatest common divisor (GCD). * @param {number} originalA  * @param {number} originalB  * @return {number}  */export default function euclideanAlgorithm(originalA, originalB) {  // Make input numbers positive.     const a = Math.abs(originalA);     const b = Math.abs(originalB);   // To make algorithm work faster instead of subtracting one number // from the other  // we may use modulo operation.     return (b === 0) ? a : euclideanAlgorithm(b, a % b);}/** * Iterative version of Euclidean Algorithm of finding greatest common divisor (GCD). * @param {number} originalA * @param {number} originalB * @return {number} */export default function euclideanAlgorithmIterative(originalA, originalB) {     // Make input numbers positive.     let a = Math.abs(originalA);     let b = Math.abs(originalB);      // Subtract one number from another until both numbers would    /  //become the same.  // This will be out GCD. Also quit the loop if one of the numbers is zero.     while (a && b && a !== b) {         [a, b] = a > b ? [a - b, b] : [a, b - a];  }   // Return the number that is not equal to zero since the last                  //subtraction (it will be a GCD).      return a || b;}`

Least common multiple

In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers `a` and `b`, usually denoted by `LCM(a, b)`, is the smallest positive integer that is divisible by both `a` and `b`. Since division of integers by zero is undefined, this definition has meaning only if `a` and `b` are both different from zero. However, some authors define `lcm(a,0)` as `0` for all `a`, which is the result of taking the `lcm` to be the least upper bound in the lattice of divisibility.

What is the LCM of 4 and 6?

Multiples of `4` are:

`4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, ...`

and the multiples of `6` are:

`6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, ...`

Common multiples of `4` and `6` are simply the numbers that are in both lists:

`12, 24, 36, 48, 60, 72, ....`

So, from this list of the first few common multiples of the numbers `4` and `6`, their least common multiple is `12`.

The following formula reduces the problem of computing the least common multiple to the problem of computing the greatest common divisor (GCD), also known as the greatest common factor:

`lcm(a, b) = |a * b| / gcd(a, b)`

A Venn diagram showing the least common multiples of combinations of `2`, `3`, `4`, `5` and `7` (`6` is skipped as it is `2 × 3`, both of which are already represented).

For example, a card game which requires its cards to be divided equally among up to `5` players requires at least `60` cards, the number at the intersection of the `2`, `3`, `4` and `5` sets, but not the `7` set.

`import euclideanAlgorithm from '../euclidean-algorithm/euclideanAlgorithm'; /** * @param {number} a * @param {number} b * @return {number} */ export default function leastCommonMultiple(a, b) {  return ((a === 0) || (b === 0)) ? 0 : Math.abs(a * b) / euclideanAlgorithm(a, b);}`

Sieve of Eratosthenes

The Sieve of Eratosthenes is an algorithm for finding all prime numbers up to some limit `n`.

It is attributed to Eratosthenes of Cyrene, an ancient Greek mathematician.

1. Create a boolean array of `n + 1` positions (to represent the numbers `0` through `n`)
2. Set positions `0` and `1` to `false`, and the rest to `true`
3. Start at position `p = 2` (the first prime number)
4. Mark as `false` all the multiples of `p` (that is, positions `2 * p`, `3 * p`, `4 * p`... until you reach the end of the array)
5. Find the first position greater than `p` that is `true` in the array. If there is no such position, stop. Otherwise, let `p` equal this new number (which is the next prime), and repeat from step 4

When the algorithm terminates, the numbers remaining `true` in the array are all the primes below `n`.

An improvement of this algorithm is, in step 4, start marking multiples of `p` from `p * p`, and not from `2 * p`. The reason why this works is because, at that point, smaller multiples of `p` will have already been marked `false`.

The algorithm has a complexity of `O(n log(log n))`.

`/** * @param {number} maxNumber * @return {number[]} */export default function sieveOfEratosthenes(maxNumber) {     const isPrime = new Array(maxNumber + 1).fill(true);     isPrime = false;  isPrime = false;      const primes = [];      for (let number = 2; number <= maxNumber; number += 1) {       if (isPrime[number] === true) {             primes.push(number);       /*       * Optimisation.       * Start marking multiples of `p` from `p * p`, and not from `2 * p`.       * The reason why this works is because, at that point, smaller  * multiples       * of `p` will have already been marked `false`.       *       * Warning: When working with really big numbers, the following line * may cause overflow       * In that case, it can be changed to:      * let nextNumber = 2 * number;       */             let nextNumber = number * number;              while (nextNumber <= maxNumber) {                 isPrime[nextNumber] = false;                 nextNumber += number;             }         }     }      return primes;}`

References:

https://github.com/trekhleb/javascript-algorithms

Full Stack SE. I love to build beautiful web apps and learn new technologies.