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
a simplisitc 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 gcd that took in two integers, called $a$ and $b$, where $a< b$. We'll
start our initial GCD guess, $g$ at $1$ via the g=1 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 of the
division. Since we are looking to see if one number divides evenly into another, we are looking
for the % 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$.
Now you try. What compound condition will you put into the if statement to test
if both a and b divide evenly into our trial GCD in variable i?
Type your code here:
See your results here:
This code will not run! You have to fill in some compound condition into the if statement to test
if both $a$ and $b$ divide evenly into our trial GCD in variable i.
Share your code
Show a friend, family member, or teacher what you've done!