The Self-Taught Computer Scientist

Introduction to Algorithms
72
How much text will there be on the last page? The last page will have 20 lines because 
50,000 % 49 
= 20
. What if you had a database with 20,000 items in it and you wanted to do something to every 
other item? One way to accomplish this is to iterate through each item and only change items with 
an even index.
Greatest Common Factor
The greatest common factor is the largest positive integer that evenly divides two or more other inte-
gers. In this chapter, you will learn, given two integers, such as 20 and 12, how to find their greatest 
common factor.
In the case of 20 and 12, you can evenly divide them both by 1, 2, and 4. Since 4 is the largest 
number, it is their greatest common factor.
Factors of 20: 1, 2, 4, 5, 10
Factors of 12: 1, 2, 3, 4, 6
One algorithm for finding the greatest common factor of two numbers is to check all possible divi-
sors to see which ones divide evenly into both numbers. For example, to find the greatest common 
factor of 20 and 12, you can start by dividing them both by 1, then 1, then 3, etc. You do not need to 
test any numbers greater than the smaller of the two numbers because a number larger than the small-
est number could not divide evenly into it. For example, a number greater than 12 does not divide 
evenly into 12.
Here is the Python code for your algorithm:
def gcf(i1, i2):
gcf = None
if i1 > i2:
smaller = i2
else:
smaller = i1
for i in range(1, smaller + 1):
if i1 % i == 0 and i2 % i == 0:
gcf = i
return gcf
gcf(20, 12)
Your function 
gfc
accepts as parameters the two positive integers of which you are looking for the 
greatest common factor.
def gcf(i1, i2):
Inside your function, you determine which of the two integers is smaller and assign it to the vari-
able 
smaller
so that you can stop testing divisors once you hit that number.

---