Do you remember a concept called the "greatest common divisor" (GCD) from math class? The name is confusing,
and it's often hard to remember the difference between this and something else called the "least common
multiple" or LCM.
Well, the GCD is a property of two numbers: it is the largest number that divides evenly
into both numbers. So, the GCD of 20 and 12 is 4. That of 54 and 24 is 6. Let's write a function that
will find the GCD of two numbers and return its result. The method we'll use here is very inefficient and definitely
way to find a GCD on a computer, but it works and it's instructive. It's also represents more-or-less
how you find GCDs in math class: by guessing and checking.
Suppose we wrote a function called
that took in two integers, called $a$ and $b$, where $a< b$. We'll
start our initial GCD guess, $g$ at $1$ via the
line. Next, we'll start a for-loop and count through
all integers from $1$ to $a$. We'll stop at $a$ because the GCD cannot possibly be larger than the smaller
of the two numbers for which we want the GCD.
Now for the good part. Remember the "remainder" or "mod" operator from this lesson
This operator, which (the
sign) divides two numbers and tells us the remainder
division. Since we are looking to see if one number divides evenly into another, we are looking
operator to give us a $0$ (zero), since a zero remainder means the two numbers
divided evenly into one another.
Now, as our for-loop is counting up the integers we'll see if it divides evenly into
both $a$ and $b$. If it does, then $i$ could potentially be the GCD, as we should "save" it
into our temporary guess, $g$. If not, we'll keep counting up to $a$ and see if we find a larger
number that divides evenly into both $a$ and $b$.