The Self-Taught Computer Scientist

Chapter 6 Math
75
12 / 8 = 1 remainder 4
8 /4 = 2 remainder 0
Here is Euclid’s algorithm in Python:
def gcf(x, y): 
if y == 0:
x, y = y, x
while y != 0:
x, y = y, x % y
return x
Your 
gcf
function accepts as parameters the two numbers of which you are looking for the greatest 
common factor.
In the first line of code, you address a boundary condition. If 
y
is 0, Python will raise an exception 
later in your program, trying to divide by 0. If 
y
is 0, you swap the contents of the variables 
x
and 
y
to solve this problem.
if y == 0:
x, y = y, x
Next, you create a 
while
loop that iterates until 
y
becomes 0.
while y != 0:
Inside your 
while
loop, this statement swaps the values in 
x
and 
y
with 
y
and the remainder of 
x
divided by 
y
.
x, y = y, x % y
When your 
while
loop ends, it means 
x % y
returned a remainder of 0. You then return the value 
of 
x
, which holds the greatest common factor of 
x
and 
y
.
return x
You can use math to prove this algorithm is logarithmic rather than linear, significantly improving 
its performance with large numbers over your original algorithm in finding the greatest common factor 
of two numbers.
Primes
A prime number is a positive integer divisible only by itself and 1. Numbers like 2, 3, 5, 7, and 11 are 
examples of prime numbers. In this section, you will learn how to write a function that determines 
if a number is a prime or not.

---

Introduction to Algorithms
76
Here is how you do it:
def is_prime(n):
for i in range(2, n):
if n % i == 0:
return False
return True
Your function 
is_prime
, takes the number you want to check whether or not it is a prime (
n)
.
def is_prime(n):
You then use a 
for
loop to iterate through every number from 2 to 
n
. You start with 2 (not 1) because 
prime numbers are still divisible by 1.
for i in range(2, n):
If 
n
is 10, your code will iterate from 2 to 9, which means 10 gets skipped (you want this to happen 
because prime numbers are also divisible by themselves).
Next, you use modulo to check whether there is a remainder when you divide 
n
by 
i
. If there is no 
remainder, you found a divisor other than 1 or the number. That means 
n
is not a prime number, so 
you return 
False
.
if n % i == 0:
return False
If you’ve iterated through your number range without finding a divisor, it means 
n
is a prime, and 
you return 
True
.
return True
Because your algorithm takes 
n
steps to complete, it is a linear algorithm.
You can improve your algorithm by ending your loop at the square root of 
n
instead of at 
n − 1
.
import math
def is_prime(n):
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
Here is why you can stop at the square root of 
n
. If 
a * b == n
, then either 
a
or 
b
has to be less 
than or equal to the square root of 
n
. Why? Because if both 
a
and 
b
are greater than the square root 

---