Generating Primes

For this assignment, you will write several programs that generate prime numbers. Our goal is to think analytically about the efficiency of the different approaches and to empirically compare the methods.

Among other contexts, prime numbers play an important role in creating strong encryption algorithms and in creating methods intended to crack such encryption algorithms. In these and other situations, we want access to a large list of prime numbers. You will write a program that generates such a sequence.

Implementation guidelines

Even more than usual, you should concern yourself with efficiency for this assignment.

If you want, you may write the required classes as separate stand-alone programs. However, you might save yourself effort if you extend each one from the previous (with the exception of the last required class, which uses a different approach).

Requirements

  1. Prime number generator, v0. Write a class, PrimeGenerator0, that generates primes. You may use the code on pages 154-155 of your text to get started, but you should implement the Iterator interface instead of extending the author's AbstractGenerator. Your iterator should report the primes in increasing order starting with 2 as the first prime and ending with the one-millionth prime. This will be the case with the subsequent variations on this task as well. As in our previous implementations of Iterator classes, the remove() method should throw an UnsupportedOperationException. For this first step of the assignment, have your constructor consume an integer argument representing the number of primes to generate. The hasNext() method can return false after producing that number of primes.
  2. Improving the efficiency, v1. Write a faster version, PrimeGenerator1, that improves on your initial code. Rather than dividing by every number from 2 up to the square-root of the candidate prime as shown in the text, you only need divide by previously found primes that are less than or equal and up to the square-root of the number.
  3. Parallelizing the generator, v2. To further improve matters, let us partition the candidates and check them independently -- in parallel when possible. Write a version, PrimeGenerator2, that checks numbers for primeness using multiple threads (where the number of threads is a commandline argument). Warning: get this working using the method for determining primeness that you employed in v1. Keep in mind the warnings mentioned in class regarding timing and lack of synchronization between threads. The results from the various threads should be combined and reported by the generator in increasing order.
  4. Sieve of Eratosthenes, v3. A solution of a very different nature is attributed to Eratosthenes, a Greek mathematician from over 2,000 years ago. Instead of dividing candidate primes by odd numbers or primes as above, the Sieve of Eratosthenes computes multiples of a known prime and ‘marks’ those multiples as not prime. Implement a class, PrimeGenerator3, that generates the first million primes using this method.
  5. Evaluating the methods. Time the initial approach on the generation of the first million primes and compare that to your other versions versions. For each generator, determine the space and time complexity and include that in your documentation.

Submission Instructions:

On your machine where you are doing your homework, create a folder called <your email name> followed by “HW9”. For example, someone with email address “cjones” would create a folder called “cjonesHW9”. Inside that folder, place plain text file(s) containing your answers to any exercises. Also, place whatever Java and documentation files are necessary for your programming project in the same folder. Finally, either tar or zip the folder so that when I extract it, the folder ”<emailname>HW09“ will be created. Finally, submit via Eureka.