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;
}
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.
Example
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.
Computing the least common multiple
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);
}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.
How it works
- Create a boolean array of
n + 1positions (to represent the numbers0throughn) - Set positions
0and1tofalse, and the rest totrue - Start at position
p = 2(the first prime number) - Mark as
falseall the multiples ofp(that is, positions2 * p,3 * p,4 * p... until you reach the end of the array) - Find the first position greater than
pthat istruein the array. If there is no such position, stop. Otherwise, letpequal 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.
Complexity
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[0] = false; isPrime[1] = 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:
