Euclid's Algorithm

Ever wanted to find the greatest common divsor (GCD) of two numbers, but were too lazy? Here's a quick solution for you!

Steps

  1. Subtract the smaller number from the bigger number.
  2. Repeat step 1 until the two numbers are equal.
  3. The number stored in these resulting two equal values is the GCD of the original two numbers.
Source 1

Diagram

Euclid's Agorithm Diagram from Khan Academy

Source 2

23:50 | 23 November 2022 | Lawrence Su | CS 400 | Week 11 HTML Activity