Ant help would be appreciated, I'm kind of confused.

Objectives

• Working with collections
• Working with iterator

Background

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:

• Sieve.java Download Sieve.java
• SieveDriver.java Download SieveDriver.java

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

______________________________________________________________________________________________________________________________________________

Sieve.java:

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