use java, and create a 3rd class. MySieve.java, which Sieve is implemented. Sieve.java below public interface Sieve { public java.util.List getPrimes(int n); }

----------

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(); } }

----

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 number 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 the pseudocode easier to read.) However, you do have to implement this algorithm for the Sieve. Using a different algorithm for the Sieve will cost you functionality points, 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. 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. We will discuss this next week.)

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 these fields.

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 insure 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.]