/**
 * This class demonstrates an clear and simple use of comments
 * with a single method that generates a list of primes.  It also
 * provides an example of how JavaDoc documentation works.
 *
 * @author CMSC 131
 * @version 1.0
 */

public class PrimeGenerator {

	/**
	 * Returns an array containing the prime numbers between 2 and 
	 * the given parameter. If there are no primes found, an array 
	 * of length 0 is returned.
	 * @param maxNumber The upper bound on the range of primes.
	 * @return An integer array holding the prime numbers.
	 */
	public static int[ ] getPrimes( int maxNumber ) {
		/* Overview: The algorithm is based on the sieve of Eratothenes.
		 * The array values[ ] is initialized to the values from 2 up to
		 * maxNumber. Each nonzero value is used to eliminate all its
		 * larger multiples by zeroing them out.  The nonzero elements
		 * are copied to the final result.
		 */
		
		/* The size of array is maxNumber + 1 (instead of maxNumber)
		 * because we want to map each number x to the entry values[x].
		 */
		int[ ]values = new int[maxNumber + 1];
		
		/* Initialize values starting at 2 */
		for ( int i = 2; i <= maxNumber; i++ ) {
			values[i] = i;
		}
		
		/* Compute the primes by removing (zeroing) multiples of primes.
		 * The upper limit could have been maxNumber, but is more
		 * efficient to stop at sqrt( maxNumber ).  
		 */
		for ( int i = 2; i <= ( int ) Math.sqrt( maxNumber ); i++ ) {
			for ( int j = 2*i; j <= maxNumber; j +=i ) {
				values[j] = 0;
			}
		}
		
		/* Count the number of remaining primes */
		int nPrimes = 0;
		for ( int i = 2; i <= maxNumber; i++ ) {
			if ( values[i] != 0 ) nPrimes++;
		}

		/* Copy the primes to the result array */
		int[ ] primes = new int[nPrimes];
		int j = 0;
		for ( int i = 2; i <= maxNumber; i++ ) {
			if ( values[i] != 0 ) primes[j++] = values[i];
		}

		return primes;
	}

}