[Exercise] Finding Prime Numbers¶
Finding prime numbers is really important to many things in computer science. Specifically, cryptography and encryption rely heavily on them to secretly encode messages!
Let’s look at how to find primes and their run times.
Naive Solution¶
The easiest way is to use a double loop and check for “primeness”
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def run(max_number):
# create list for saving the primes
found_primes = []
# loop over the numbers
for first_number in range(2, max_number+1):
# create a boolean to save the result
is_prime = True
# now go over all numbers smaller than it
for second_number in range(2, first_number):
if first_number % second_number == 0:
is_prime = False
if is_prime:
found_primes.append(first_number)
return found_primes
|
What is slow about this solution? What could be fixed? What can be taken out?
Exercise¶
Turn the most inner loop into a second function:
1 2 3 4 5 6 7 8 9 10 11 12 13 | def check_primeness(some_number):
# write this part; for now just defaulting to false
return False
def run(max_number):
# create list for saving the primes
found_primes = []
# loop over the numbers
for first_number in range(2, max_number+1):
is_prime = check_primeness(first_number)
if is_prime:
found_primes.append(first_number)
|
Sieve of Eratosthenes¶
The Sieve of Eratosthenes is an ancient way of finding prime numbers.
The description is fairly simple:
- Start with a list of all numbers between 2 and the max number.
- Loop through the numbers, starting with 2.
- With each number, “mark” all of its multiples (for 2, it’d be 4, 6, 8, etc)
- Continue the loop with the next largest number not marked.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | def run(max_number):
# create list of all numbers
numbers = []
for i in range(max_number):
numbers.append(i)
current_number = 2
while current_number < max_number:
# go through and mark 2*current_number, 3*current_number, etc
for multiple in range(2, max_number):
new_number = current_number * multiple
if new_number < max_number:
numbers[new_number] = -1
# find the next "current_number"
finding_next = True
while finding_next and current_number < max_number:
current_number += 1
if numbers[current_number] != -1:
finding_next = False
for i in range(2, max_number):
if numbers[i] != -1:
print("{} is a prime number!".format(i))
|
What parts of this are slow? What parts are doing extra work that doesn’t need to be done?
Exercise¶
I have moved the code into separate functions. Use the fact that you can return early to make the functions faster.
Hint: mark_multiples
and get_next_number
can both be made faster.
Hint: Determine when the function should be over, exit at that point.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | def mark_multiples(current_number, max_number, numbers):
# go through and mark 2*current_number, 3*current_number, etc
for multiple in range(2, max_number):
new_number = current_number * multiple
if new_number < max_number:
numbers[new_number] = -1
def get_next_number(current_number, numbers):
# find the next "current_number"
finding_next = True
while finding_next:
current_number += 1
if numbers[current_number] != -1:
finding_next = False
return current_number
def print_prime_list(numbers):
for i in range(2, max_number):
if numbers[i] != -1:
print("{} is a prime number!".format(i))
def run(max_number):
# create list of all numbers
numbers = list(range(2, max_number))
while current_number < max_number:
mark_multiples(current_number, max_number, numbers)
get_next_number(current_number, numbers)
print_prime_list(numbers)
|