Euclid’s Algorithm

Euclid’s Algorithm is an efficient way to find the greatest common factor of a number. First, you divide the number x by y, to find the remainder. Then you divide again, using the remainder for y and the previous y as the new x. You continue this process until the remainder is 0. The last divisor is the greatest common factor.

For example:

20 / 12 = 8 12 / 8 = 4 8 / 4 = 2 // remainder 0 so the GCF is 4

The greatest common factor of 20 and 12 is 4

def greatestCommonFactor(x,y):
  if y == 0:
    x,y = y,x
  while y != 0:
    x,y = y,x % y
  return x

Keyboard shortcuts