Skip to content
Back to AlgorithmsAll lessons

Algorithms

Euclid's GCD

O(log(min(a, b))) time — surprisingly fast, since each step shrinks the numbers quickly · O(1) space.

The idea, in plain English

Imagine two ropes, one 48 inches long and one 18 inches long. You want the longest ruler that measures both exactly, with nothing left over. Euclid's trick: measure the shorter rope against the longer one, look at what is left over, and repeat using that leftover as your new short rope. Keep going until nothing is left over. The last rope length you used is the greatest common divisor (GCD) — the biggest number that divides both original numbers evenly.

How it works

  1. 1Take two numbers, a and b.
  2. 2Divide a by b and find the remainder r (that is a % b).
  3. 3Replace a with b, and b with r. Repeat until b becomes 0 — then a is the GCD.

When you'd use it

Use it whenever you need the largest shared factor of two numbers — simplifying a fraction to its lowest terms, finding a common ratio, or as a building block inside more advanced math and cryptography algorithms.

Common beginner mistakes

  • Assuming it needs sorted or special input. It works on any two non-negative whole numbers, in either order.
  • Forgetting that gcd(0, n) should just return n. The loop already handles this correctly, but it is easy to get this wrong if you special-case it by hand.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
GCD of 48 and 18: 6
GCD of 17 and 5: 1

See it in motion

Watch the pair shrinkgcd(41, 25)O(log(min(a, b))) time — surprisingly fast, since each step shrinks the numbers quickly · O(1) space.

Find the GCD of 41 and 25. Divide the larger by the smaller and read the remainder.

41
a
25
b
—
Remainder
—
GCD
Copies of b inside aRemainder (next divisor)GCD

Not sure this is the right topic? See the learning paths → or where this leads →