You have been hired to generate a list of prime numbers up to some user-specified bound. To do this, we are going to implement of the watershed algorithms of ancient Greek mathematics. This technique is called the Sieve of Eratosthenes. It is named for its discoverer, Eratosthenes, who liven in Ptolemaic Alexandria in the third century BCE. Recall that a prime number is a positive integer that is evenly divisible only by itself and one. The Sieve of Eratosthenes works by removing the multiples of prime numbers (as you find them) from a list of candidates. So, what's left in the sieve after you remove the multiples are prime numbers.

Minimal Version Starting Point

Download the starting point code:

---------------------------------------------------------------------------------

first is SieveDriver.java

public class SieveDriver { private java.util.Scanner scan; private Sieve theSieve; public void go() { java.util.List primes; int n = getNumber(); primes = theSieve.getPrimes(n); printPrimes(n, primes); } public int getNumber() { System.out.print("Enter the upper bound: "); int n = scan.nextInt(); return n; } public void printPrimes(int bound, java.util.List list) { System.out.println("The primes up to " + bound + " are:"); for(int i = 0; i < list.size(); i ++) { System.out.print(list.get(i) + " "); } System.out.println(); System.out.println(); } public static void main(String[] args) { new SieveDriver().go(); } }

and second is Sieve.java

public interface Sieve { public java.util.List getPrimes(int n); }

------------------------------------------------------------------------------------------

The Algorithm - Sieve of Eratosthenes

Here is the algorithm (directions) for the Sieve of Eratosthenes. Let's say we're looking for all the prime numbers that are not bigger than N. (In the pseudocode which follows, we are using explicit names. You do not have to use these names. The use of specific names just makes thepseudocode easier to read.) However, you do have to implement this algorithm for the Sieve. Using a different algorithm for the Sieve will cost you a lot of functionality points.

• Create a list of all the potential prime numbers (from 2 up to N).
  • We're including all the numbers between 2 and N because anyone of them might be a prime.
  • We're excluding one (1) because it's not a prime.
  • Let's call this list numberList.
• Create a list of the prime numbers that we have found.
  • This list starts out empty.
  • Let's call this list primeList.
• Loop:
  • Take the lowest (first) number out of numberList. This is a prime number. Let's call it currentPrime.
  • Add currentPrime to primeList.
  • Remove all the numbers in numberList that are evenly divisible by currentPrime.
• Go back to Loop as long as currentPrime is less than some limit M.
• All the rest of the values in numberList are also prime. Move them to primeList.

Here are some notes about the algorithm.

• The limit for the loop is M. This value is the square root of N.
• Remember that when some number j is evenly divisible by k, the remainder of that division is zero.

For another explanation of the algorithm (including a nifty graphic representation of the algorithm in action), visit the Wikipedia article (http://en.wikipedia.org/wiki/ (Links to an external site.)Sieve_of_Eratosthenes (Links to an external site.)). In the Wikipedia write-up, 'List A' corresponds to 'numberList' and 'List B', to 'primeList'.(There is a minor algorithmic difference in the animation in Wikipedia.)

Create a new class to implement the Sieve interface. Name your class MySieve. Implement the Sieve interface using one of the List implementations from java.util, namely java.util.ArrayList or java.util.LinkedList.

Update SieveDriver

Even though SieveDriver compiles, it will not run. The fields in this class are never instantiated. Add a parameterless constructor to initialize thesefields.

Also, update the printPrimes method to use java.util.Iterator, rather than the get method of List.

Test Cases Create test cases to insure that the sieve is implemented correctly. Here are two test cases to get you started: N Primes 10 2 3 5 7 100 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

You will need to create at least 3 additional test cases. Include your additional test cases in the report. Include both the input value and the expected results in the report.

Javadoc comments The downloaded files do not contain any comments. Add Javadoc comments to these files. (Yes, this is one way that I can ensure that you have read and understand the code that you're working with.)

The only change to Sieve.java shall be the addition of Javadoc comments.

Standard Version

For the Standard version, implement the following enhancements to the Minimal version:

• Update the getNumber method of SieveDriver so that it will perform input validation. When the user types something which is not a non-negative integer, the method should report the error and prompt for new input.
• Update the go method of SieveDriver to ask repeatedly for upper bounds. Use the value zero to indicate that the application shall end.
• For the Minimal Version, you have already updated the printPrimes method of SieveDriver to use the Iterator interface to get the values from the list. Now update printPrimes to format the output: 12 numbers per line. Following the list of primes, print out the percentage of the numbers between 1 and N that are prime. This value shall be rounded to the nearest integer value.

Sample run Please enter the upper bound (0 to exit): 10 Here are the primes between 2 and 10 2 3 5 7 40% of the numbers between 1 and 10 are prime. Please enter the upper bound (0 to exit): 100 Here are the primes between 2 and 100 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 25% of the numbers between 1 and 100 are prime. Please enter the upper bound (0 to exit): 0

Explain M In the algorithm for Sieve, we loop. At first glance, it looks like we should just keep repeating this until numberList is empty. While this would work, it is not optimal. The optimal solution is to loop as long as currentPrime is less than M, where M is N. [fodder: Explain why we can stop processing the sieve when currentPrime becomes greater than or equal to M. That is, explain why, at this point, everything left in numberList is prime.]

Challenge Version It is sometimes hard to convince students that there is a difference between using the methods of the List interface and using the methods of the Iterator interface when working with the values within a List. For the Challenge option, we'll collect a little empirical data about the difference between using List methods and the Iterator methods, for both ArrayList and LinkedList.

The time consuming part of the Sieve algorithm is the loop, where we repeatedly work through the numberList with each new value ofcurrentPrime. The work is fetching the values from numberList and removing them if they are multiples of currentPrime.

To measure the elapsed time, we will use System.nanoTime. This returns a long value representing the JVM internal clock counting nanoseconds. Rather than reporting nanoseconds, we will report milliseconds. Here is the pseudo-code for a measurement:

long start = System.nanoTime(); answer = sieve_implementation(n); long end = System.nanoTime(); long elapsed = (end - start) / 1000000; // check accuracy if(answer.size() == expected) { print out elapsed time } else { report error in algorithm }

where n is 10,000 or 20,000 and expected is 1,229 or 2,262, respectively.

The differences become apparent as the value of N increases. For this exercise, we'll look at two values for N: 10,000 and 20,000. There are 1,229 primes less than 10,000 and 2,262 primes less than 20,000. Do not print out the primes. It is sufficient to check the number of values returned by the sieve of Eratosthenes algorithm. Printing is much more time consuming than calculating. [fodder: Try running the Sieve implementation you created for the Standard version of the assignment for some relatively small value of N, like 1,000. Use System.nanoTime to time how long the call to getPrimes takes and to time how long it takes to print out the 168 resulting primes.]

Create a separate Java application for the Challenge portion. Because this is a timing study, the program structure will be different than of a "normal" program. For the timing study, we want to minimize the overhead, which would "contaminate" our measurements. That is, do not create four separate classes each of which implements the Sieve interface. Instead, write the four implementations as methods within the same class. [fodder: Could/should these be static methods?] Also, do not worry about repeated code and refactoring in creating these four methods. Refactoring will add method call overhead which will add the the time that you are measuring.

Now, what exactly are the four methods? Well, we're working with two orthogonal sets of characteristics.

2. the implementation of java.util.List:

2. 2. java.util.ArrayList
   4. java.util.LinkedList
5. the methods used to access and modify the contents of the List:\
   2. the get and remove methods of java.util.List
   4. the next and remove methods of java.util.Iterator

So, there are four possible combinations:

1. java.util.ArrayList using get and remove methods of java.util.List 2. java.util.ArrayList using next and remove methods of java.util.Iterator 3. java.util.LinkedList using get and remove methods of java.util.List 4. java.util.LinkedList using next and remove methods of java.util.Iterator

So, the class you create for this Challenge option will need to support these four implementationsof the sieve of Eratosthenes. That means the class will have four methods for the four implementations. They have the same parameter profile, so they will need to have novel names, rather than be overloaded. Needless to say, this means that they cannot be implementations (in the sense of the Java keyword implements) of the Sieve interface that you used in the main part of this assignment.

In the application method, call each of the four sieve implementations with the two test values:10,000 and 20,000. So, you'll have 8 separate runs of the sieve: 4 generating 1,229 primes and 4 generating 2,262 primes. 1. java.util.ArrayList using get and remove methods of java.util.List, N = 10,000 2. java.util.ArrayList using next and remove methods of java.util.Iterator, N = 10,000 3. java.util.LinkedList using get and remove methods of java.util.List, N = 10,000 4. java.util.LinkedList using next and remove methods of java.util.Iterator, N = 10,000 5. java.util.ArrayList using get and remove methods of java.util.List, N = 20,000 6. java.util.ArrayList using next and remove methods of java.util.Iterator, N = 20,000 7. java.util.LinkedList using get and remove methods of java.util.List, N = 20,000 8. java.util.LinkedList using next and remove methods of java.util.Iterator, N = 20,000