6.12 LAB: Sieve of Eratosthenes

In this lab, you are going to implement "Sieve of Eratosthenes" (SoE) into a Python function.

The input of SoE is an integer n, which denotes the maximum integer you are going to test whether or not every integer less than or equal to this number is a prime number.

The algorithm of SoE is described as follows (Photo credit: Wikipedia https://en.wikipedia.org/wiki/SieveofEratosthenes#/media/File:SieveofEratosthenes_animation.gif):

First of all, a prime number is a natural number that has exactly two distinct natural number divisors: 1 and itself.

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

Below is what you need to implement in function SieveOfEratosthenes()

    Create a list, or preferably a Python dictionary, corresponds to consecutive integers from 2 through n: (2, 3, 4, …, n). You might want to initialize what you've just created with a long array of Boolean True values to denote that all integers are initially assumed to be prime numbers (and sift away composite numbers in the following steps). For dictionaries, key the dictionary with (2, 3,4,…,n) and intialize all values to True.

prime_number_table = [True for _ in range(2, n+1) ] # This is a list comprehension example.
prime_number_table = {k: True for k in range(2, n+1) } # This is a dictionary comprehension example.

    Initially, let p equal 2, the smallest prime number.
    Enumerate the multiples of p by counting to n from 2p in increments of p, and mark them in the list (these will be 2p, 3p, 4p, …; the p itself should not be marked). For example, whenever you find the first prime number "2," it automatically follows that all multiples of 2 are composite numbers (i.e. the exact opposite of prime number). So mark 4, 6, 8, 10, 12 as False in your list or dictionary. Repeat the process whenever you find another prime number.

# Following code snippet only works with one particular definition of prim_number_table provided above.
prime_number_table[2*2] = False
prime_number_table[2*3] = False
prime_number_table[2*4] = False
prime_number_table[2*5] = False
...

The second round of sifting away composite number should do:

# Following code snippet only works with one particular definition of prim_number_table provided above.
prime_number_table[3*2] = False
prime_number_table[3*3] = False
prime_number_table[3*4] = False
prime_number_table[3*5] = False
...

    Find the first number greater than p in the list 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.

Example of input-output pair is shown below:

When input is

10

Your program is expected to output:

[2, 3, 5, 7]

When input is

100

Your program is expected to output:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]\n

Since the list of prime number starts from 2. Whenever you get an input less than 2, return "invalid input"

When input is

1

Your program is expected to output:

invalid input

In addition, your program should reject any invalid user input by print out "invalid input" whenever it receives a floating point number or any other input which doesn't make sense to "Sieve of Eratosthenes"

When input is

3.7

Your program is expected to output:

invalid input