Use properties of divisibility, primes and remainders to avoid brute force.
Used for
48 mod 18 = 12
18 mod 12 = 6
12 mod 6 = 0: gcd = 6
What is gcd(20, 8)?
Not quite. 20 mod 8 = 4, then 8 mod 4 = 0, so the answer is 4.
Step 1 of 5
Goal: the greatest common divisor of 48 and 18. Key fact: the answer stays the same if you replace (a, b) with (b, the remainder of a ÷ b). The numbers shrink quickly.
Step 2 of 5
48 ÷ 18 leaves remainder 12, so carry on with (18, 12).
Step 3 of 5
18 ÷ 12 leaves 6: carry on with (12, 6).
Step 4 of 5
12 ÷ 6 leaves 0, so stop: the answer is 6. Remainders shrink fast, so only a few steps (O(log n)). The least common multiple follows: lcm = a × b ÷ gcd. These are number theory tools.
Step 5 of 5
Your turn.
Euclidean algorithmLeast common multiplePrimality TestSieve of EratosthenesPrime FactorsFast Powering AlgorithmFactorialHorner's MethodSquare Root (Newton's Method)
const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));const lcm = (a, b) => (a / gcd(a, b)) * b;