Eratosthenes of Cyrene lived approximately 275-195 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..
Please note: You must use this algorithm for this assignment. No other algorithm for finding prime numbers will be accepted for this assignment, although there are plenty of other and more sophisticated algorithms available!
Here are some guidelines:
- Create a list of 1,000 values ... all of which are set to zero (hint: use list repetition)
- This list represents the numbers 0 to 999 (based on the indexes in the list)
- Your goal is to set all non-prime numbers in the list to 1. You can do that by using the following algorthm:
- Start by setting the first two values (index positions 0 and 1) to 1. 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
|
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
- Now, move on to the item in position #2 of the list. This item is currently zero, meaning that the number is prime. We now need to mark all future items that are evenly divisible by two as "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 a 1 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 1. After this step your list should look as follows:
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
1
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
- Now, perform the exact same process for the element with an index of 3 - there is currently a zero in postion #3, so we are going to mark all multiples of 3 (starting with 6) with a value of 1. If your program finds an element which is already 1, there is nothing further to do for the item (i.e. position 6 will already be marked with a 1 at this point - we can simply skip this element and move onto the next one in the sequence (9) and mark it with a 1)
- Next, you can perform the exact same process on the item with an index of 4 ... however, since 4 is already set to 1, 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.
- Here is the pattern as you move from one item in the list to the next: If that item has a value of 0, perform the process. If it is already 1, skip the process. It is important that you understand why you should skip this process when the element you are considering is already 1.
- 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 0 ... and 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) - this can be done by essentially iterating over the list and checking the value of each item -- if there is a zero in this position, print it out as a prime number. If there is a one in this position you can skip it since it is not prime.
Here is a "visual" example:Suppose you want to find all prime numbers between 2 and 10, inclusive (your actual homework program will really look from 2 to 1000). Your list might look like this when you start :
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
Start by looking at the element with an index of 2 (as described above). Find all of the items with an index that is a multiple of 2 and change all those items to 1. This is what you would get, because 4, 6, 8, and 10 are multiples of 2:
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
1
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
Now move on to the item with an index of 3 and find all of the items whose index is a multiple of 3. Change those items to 1. (If you find an item which is already 1, it's OK to "change" it to 1 ... It just stays 1, which is fine). This is what you get, because 6 and 9 are multiples of 3:
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
1
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
Now move on to the item with an index of 5. That item is still 0, so perform the process. That is, find all of the items in the list whose index is a multiple of 5, and change all those items to 1. In this case, nothing has changed because the item with an index of 10 was already set to 1:
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
1
|
1
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
Looking at the final list just above, note which items (starting with an index of 2), still contain the value 0. You come up with items that have an index of 2, 3, 5, and 7. These are precisely the prime numbers you are looking for.Your program should print out all of the prime numbers that you have found in neatly aligned columns (with up to 10 prime numbers on every row).Notes on Efficiency:Efficiency is important here; Hint: 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 1, what does this tell you about the multiples of that item's index?
- 800, for example, cannot have any multiples less than or equal to 1000. Generalize this idea to make your program much more efficient.
This program should be named as follows: LastnameFirstname_assign8_sieve.py (for example, DeenaEngel_assign8_part1.py)