The Self-Taught Computer Scientist

Chapter 6 Math
77
of 
n
, then 
a * b
has to be greater than 
n
and, therefore, cannot equal 
n
. So, you cannot have two num-
bers, 
a
and 
b
, where both are larger than the square root of 
n
, multiply to become 
n
since 
a * b
will 
be greater than 
n
. Since one divisor must be less than or equal to the square root of 
n
, you don’t have 
to test up to 
n
. Instead, you can stop at the first integer larger than the square root of 
n
. If you don’t 
find any number less than or equal to the square root of 
n
that divides 
n
evenly, then you won’t find 
any number that does.
You can easily modify your program to print a list of all the prime numbers within a number range.
def is_prime(n):
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
def find_primes(n):
return [i for i in range(2, n) if is_prime(i)]
First, you create a new function called 
find_primes
, which takes as a parameter 
n
, which is the 
number up to which you are looking for primes.
You then use a list comprehension to iterate from 2 to 
n
, only adding items to your new list if 
is_prime
returns 
True
.
return [is_prime(i) for i in range(2, n)]
Your algorithm to find all the prime numbers in a number range calls your linear 
is_prime
function 
inside a loop, which means it has an O(
n**2) time complexity and is not very efficient. The algorithm 
you learned in this chapter is not the only algorithm for finding prime numbers, though. There are 
other, more complicated algorithms to find prime numbers that have a more efficient time complexity 
you can learn as well.
Vocabulary