The Self-Taught Computer Scientist

Chapter 6 Math
73
if i1 > i2:
smaller = i2
else:
smaller = i1
Next, you use a 
for
loop to test each divisor from 1 to the value of the variable 
smaller
plus 1 (so 
that you also test the smaller number).
for i in range(1, smaller + 1):
Next, you use an 
if
statement to see if the divisor divides evenly into both integers. If it does, you 
assign the divisor to the variable 
gcf
.
if i1 % i == 0 and i2 % i == 0:
gcf = div
Just because you found one common factor doesn’t mean you’ve found the greatest common factor, 
however. If you find another, larger divisor, you set 
gcf
to it the next time around your loop. That 
way, when your loop ends, 
gfc
will contain the largest divisor.
There is a problem with your code, though. What if one of the integers is 0?
print(gcf(0, 22))
>> None
Your program returns the wrong answer when one of the integers is 0.
Your code’s inability to handle 0 is an example of a boundary condition: input outside of the input 
you expected your program to receive. When calculating the greatest common factor of two numbers, 
if either of the integers is 0, the greatest common factor is the other integer. For example, the greatest 
common factor of 0 and 12 is 12.
When you are writing algorithms, you should always think about what sort of unexpected input 
could break it. In this case, your algorithm is incorrect when the input is 0. Here is how to modify 
your program to return the correct output if either of the integers is 0:
def gcf(i1, i2):
if i1 == 0:
return i2
if i1 == 0:
return i1
if i1 > i2:
smaller = i2
else:

---

Introduction to Algorithms
74
smaller = i1
for divisor in range(1, smaller + 1):
if(i1 % divisor == 0) and (i2 % divisor == 0):
gcf = divisor
return gcf
Your program also cannot handle negative numbers, so you should add a test at the beginning to 
ensure both numbers are positive.
def gcf(i1, i2):
if i1 < 0 or i2 < 0:
raise ValueError("Numbers must be positive.")
if i1 == 0:
return i2
if i1 == 0:
return i
if i1 > i2:
smaller = i2
else:
smaller = i1
for divisor in range(1, smaller+1):
if(i1 % divisor == 0) and (i2 % divisor == 0):
gcf = divisor
return gcf
Your greatest common factor code is linear because your algorithm solves the problem in 
n
steps. 
Linear is not bad, but there is a better way to solve this problem.
Euclid’s Algorithm
A more efficient solution for finding the greatest common factor is called Euclid’s algorithm. First, you 
divide one number, 
x
, by the other number, 
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, to find the greatest common factor of 20 and 12, you start by dividing 20 by 12 (or 
12 by 20) and get the remainder: 8. Next, you divide 12 by the remainder, and 12 divided by 8 pro-
duces a remainder of 4. Now, you divide 8 by 4. This time, there is no remainder, which means 4 is 
the greatest common factor.
20 / 12 = 1 remainder 8

---