Homework #1: Prime numbers

Problem

The following pseudocode will build an array, a, containing the first n prime numbers:

Set the first element of a to the lowest prime number (2).
For each odd number, test, starting at 3:
    For each element, p, in a:
        Compute the remainder of test/p.
    If the remainder was non-zero for every p:
        Append test to a.
	If the length of a equals n:
		break

Assignment

Create a Java program, Prime.java, to implement this algorithm. The program should accept one command-line argument, the number of primes to generate (n). It should respond by printing the first n prime numbers, followed by a message stating the n-th prime number. If more than 10 prime numbers are requested, the program should print only the first five and the last five, separated by a line displaying an ellipsis ("...").

For example:

$ java Prime 13
   2
   3
   5
   7
   11
   ...
   23
   29
   31
   37
   41
The 13-th prime number is 41.
$

Other requirements:

• Your program should generate the entire array of prime numbers before printing any of them, rather than printing them "on the fly".
• For n equal to 1, 2, or 3, the output should read "first", "second", or "third" rather than "1-th", "2-th", or "3-th". (Feel free to generalize this to other numbers.)
• If no command-line argument is supplied, the program should print a helpful message to the Java error stream, System.err, and exit.
• Use int (4-byte) variables throughout the program.
• Your program should make no assumption about the maximum number of primes which can be requested. For example, you cannot simply define a as an 8000-element array.
• If the command-line argument is less than one, assume that it is equal to one.

Due date: The program is due at the beginning of class on 16 September.

Turn in: A listing of your program, and a printout of a terminal session in which you compile the program and run it. You must run the program once with no command-line argument and once for each of the following inputs: 1, 3, 4, 77, and 8000. (Use the Unix script command to record the relevant part of your terminal session.)