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.

Steps

  1. Add a method to the code that will implement the sieve of Eratosthenes method for computing primes.
  2. Test your method to ensure that it works correctly. Print out or attach the list of primes generated by your program for =100.
  3. 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?)
  4. 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?)

Algorithm

  • Create a list of consecutive integers from 2 through n: (2, 3, 4, …, ).
  • Initially, let p equal 2, the smallest prime number.
  • Enumerate the multiples of p by counting in increments of p from 2p to , and mark them in the list (these will be 2p, 3p, 4p, …; p itself should not be marked).
  • Find the smallest number in the list greater than p that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime) and repeat from step 3.
  • When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.

Requirements

import math
import matplotlib.pyplot as plt
from timeit import default_timer as timer

Source files can be found here.

View my cv.