Python problem!

Eratosthenes of Cyrene lived approximately 275195 BC. He was the first to accurately estimate the diameter of the earth. For several decades he served as the director and chief librarian of the famous library in Alexandria. He was highly regarded in the ancient world, but unfortunately only fragments of his writing have survived.

The algorithm described for this assignment is known as the Sieve of Eratosthenes. The algorithm is designed to find prime numbers within a given range. You are required to use the Sieve of Eratosthenes algorithm for this assignment. No other algorithm for finding prime numbers will be accepted, although there are plenty of others available.

Getting Started

Begin by inputting a range of numbers to test. Our goal is to examine these numbers and determine which of the numbers in this range are prime. Your lowest number will be 0 and your highest number will be n.

Create a list of n + 1 values where n is the highest number you want to test. Populate each element in this list with the string, P for prime. We will start by assuming all numbers in the given range are prime. For example, if you were testing all numbers between 0 and 10, your list would look like this (the top row represents index positions).

0	1	2	3	4	5	6	7	8	9	10
P	P	P	P	P	P	P	P	P	P	P

Your goal is to set all non-prime numbers in the list to N (for non-prime). You can do that by using the following algorithm. Start by setting the first two values (index positions 0 and 1) to N. This lets us record that 0 and 1 are not prime numbers. After this step your list should look like the following.

0	1	2	3	4	5	6	7	8	9	10
N	N	P	P	P	P	P	P	P	P	P

Now, move on to the item in position #2 of the list. This item is currently set to P, meaning that the number is prime. We now need to mark all future items that are evenly divisible by two as N, not prime. You can do this by reading through the entire list starting at 4 (the first multiple of 2), 2 at a time, so that every element that is read contains an index which is a multiple of 2, and store an N for that element. This will result in a list in which all of the items whose index is a multiple of 2 will have a value of N. After this step your list should look as follows.

0	1	2	3	4	5	6	7	8	9	10
N	N	P	P	N	P	N	P	N	P	N

Now, perform the exact same process for the element with an index of 3there is currently a P in postion #3, so we are going to mark all multiples of 3 (starting with 6) with a value of N. If your program finds an element which is already N, there is nothing further to do for the item (i.e. position 6 will already be marked with an N at this pointwe can simply skip this element and move on to the next one in the sequence, 9, and mark it with an N).

You can perform the exact same process on the item with an index of 4however, since 4 is already set to N, there is no need to check its multiples and your program could just move on to the next item, which has an index of 5.

Processing and Output

Here is the pattern as you move from one item in the list to the next: If that item has a value of P, perform the process. If it is already N, skip the process. Try to understand why you should skip this process when the element you are considering is already N.

Now, repeat this process over and over. When you have finished, you will find that there are array items which still have a value of P. Those items index numbers are the prime numbers which you are seeking. Your program should print out all of the prime numbers which you have found in neatly aligned columns, with up to 10 prime numbers on every row as in the following example. This can be done by iterating over the list and checking the value of each itemif there is a P in this position, print it out as a prime number; if there is an N in this position you can skip it since it is not prime.

Enter a number range: 250 All prime numbers from 0 to 250 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 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241

On Efficiency

Efficiency is important for this program. You do not need to perform the process described above on all items of the list for two different reasons.

If an item in your list has already been set to N, what does this tell you about the multiples of that items index?

Certain numbers dont need to be tested. 800, for example, cannot have any multiples that are less than or equal to 1000. Generalize this idea to make your program even more efficient.