Module $01$ Coding Assignment: The Eratosthenes Method

Purpose

Prime numbers form an integral part of cryptographic frameworks as they are the basic building blocks of some of our cryptography algorithms. There are many ways to compute prime numbers. In this homework, you will modify a Python program that computes the prime numbers in a range, then you will analyze its output. Your modifications will include implementing an additional algorithm $($called the sieve of Eratosthenes method$)$ to compute primes. In addition to giving you some practice with prime number generation, this homework will also serve as a gentle introduction to structured programming in Python.

Instructions

Before starting this assignment, do the following:

import math

import matplotlib.pyplot as plt

from timeit import default$\_$timer as timer

$\text{'}\text{'},$ Provide your implementation of the Sieve of Eratosthenes here

$\text{'}\text{'}\text{'}$

def eratosthenes $($n$)$:

return None

$\text{'}\text{'},$ Function to determine if a number is a prime

Checks all values from $2$ to square root of number to find a divisor for number

Can you spot the inefficiency in the loop below?

How might you fix that?

def isPrime $($num$)$:

stop $=$ int$($math$.$sqrt $($num$))$

isPrime $=$ True

for j in range$(2,$ stop$+1)$:

if num$8$j $==0$:

return False

return True

$\text{'}\text{'}\text{'}$BruteForce approach to print all primes in range $2$ to n $\text{'}"\text{'}$

def brute$\_$force$($n$)$:

list $=[]$

for i in range $(2,$n$+1)$:

if isPrime$($i$)$:

list.append$($i$)$

return list

#Code to time the performance of brute$\_$force

n $=200000$

start $=$ timer$()$

list $=$ brute$\_$force$($n$)$

end $=$ timer$()$

print$("$brute$\_$force:",end $-$ start$)$

print$($list$)$

#plot some statistics

plt$.$hist$($list$,$ density$=$False, bins$=100)$

plt$.$title$(\text{'}$Prime Distribution'$)$

plt$.$show$()$Download the primes.py Download primes.pyfile.

Rename the file to $\_$primes.py $($without the angle brackets$).$

Open the file using the Virtual Lab or $[$HIGHLY recommended$]$ on your computer if you have Python installed.

Once you've completed those steps, take a closer look at the program. The program does the following:

Uses a brute force algorithm to compute all primes from $2$ to

Measures the time taken by the algorithm

Plots the frequency of the prime numbers in the given range

As mentioned earlier, you will need to modify this program. Complete steps $14.$

Add a method to the code

that will implement the sieve of Eratosthenes method for computing primes. The sieve algorithm as described on Wikipedia is included in the callout below.

Test your method to ensure that it works correctly. Print out or attach the list of primes generated by your program for

$=100.$

Add code that will call your new method along with the brute force method and measure the time taken for both algorithms to generate for

$=200,000.$ Comment on the results you see. $($e$.$g$.,$ Which is greater or smaller? Why does one take more time than the other? How might this scale if we increased n significantly, say to $10$ million?$)$

Plot the primes generated by your method in a histogram. You may replace the plot of the brute force algorithm already displayed. Comment on the distribution of primes. $($e$.$g$.,$ Are the primes evenly distributed? Do they tend to occur in a specific range plotted?$)$

Submission

Please submit your answers as a $.$zip file. The following items should be included in the $.$zip file:

The modified primes.py file $($remember to rename it according to the instructions$)$

A text file that has your answers$/$comments to questions $2,3,$ and $4$ above.