// Primes.java

import java.util.List;
import java.util.Iterator;
import java.util.LinkedList;
import java.io.PrintStream;

/**
 *
 * The class Primes implements a version of Erastothenes' sieve in
 * order to find the first n primes. The algorithm is basically:
 *
 *   Initialize the list of primes to contain 1 and 2.
 *   Initialize ntr to the last prime in the list (2).
 *   Initialize the candidate prime to 3.
 *
 *   While (the list of found primes has less than n elements) Begin
 *
 *     Let r be the highest integer that is less or equal to the 
 *           square root of the candidate.
 *
 *     Let ntr be the highest prime that is less or equal to r.
 *
 *     Examine the primes p between 2 and ntr: if for any p
 *     (candidate / p) leaves no remainder, the candidate is not prime.
 *   End
 *
 * The commandline argument of the program is number of primes to find.
 *
 * @author Fredrik Kilander fk@dsv.su.se
 */
public class Primes {

  /**
   * Holds the list of found primes.
   */
  protected LinkedList<Integer> foundPrimes;

  /**
   * The number of primes we are set to find.
   */
  protected int nofPrimes = 10;

  /**
   * Creates a new instance of Primes, set to find the specified
   * number of primes, starting at 1.
   *
   * @param nofPrimes The number of primes to find.
   */
  public Primes (int nofPrimes) {
    this.nofPrimes = nofPrimes;
    foundPrimes = new LinkedList<Integer> ();
  }

  /**
   * Prints a table of the found primes, breaking the line every 8th
   * prime.
   *
   * @param pw  The PrintStream to use for output.
   */
  public void printPrimes (PrintStream pw) {
    int itemCounter = 0;

    pw.println ("Primes found :");

    for (Iterator<Integer> ii = foundPrimes.iterator (); ii.hasNext ();) {
      pw.print (ii.next ().intValue () + " ");
      itemCounter++;
      if ((itemCounter % 8) == 0) {
	pw.println ();
      }
    }
    if ((itemCounter % 8) != 0) {
      pw.println ();
    }
  }

  /**
   * Prints the table of found primes on the default output (System.out).
   */
  public void printPrimes () {
    printPrimes (System.out);
  }

  /**
   * Searches for primes until the specified number has been met (or
   * we run out of memory).
   */
  public void search () {
    int ntrPos = 1;		// index into list of found primes
    int candidate = 3;		// our next candidate prime

    foundPrimes.add (1);	// 1 is a known prime
    foundPrimes.add (2);	// 2 is a known prime

    Integer nearestToRoot = foundPrimes.get (ntrPos);

    while (foundPrimes.size () < nofPrimes) {

      // Find the closest integer less or equal to the square root of
      // candidate.

      int root = (int) Math.floor (Math.sqrt ((double) candidate));

      // If candidate is not prime, then there exists a prime equal
      // to, or smaller than root which divides candidate evenly.  The
      // while loop below searches for the largest prime (found so far)
      // less or equal to root, to establish an upper bound for the trial
      // by division.

      while ((nearestToRoot.intValue () < root) &&
	     (ntrPos < foundPrimes.size ())) {
	if (foundPrimes.get(ntrPos+1).intValue () <= root) {
	  ntrPos++;
	  nearestToRoot = foundPrimes.get (ntrPos);
	}
	else {
	  break;
	}
      }

      // Now we know which primes we need to examine against candidate
      // (the index of the highest possible prime is in ntrPos). We
      // assume that candidate is prime, and then see if we can prove
      // that assumption to be wrong.

      boolean isPrime = true;

      for (Iterator<Integer> ii =
	     foundPrimes.subList (1, ntrPos+1).iterator ();
	   ii.hasNext ();) {
	if ((candidate % ii.next ().intValue ()) == 0) {
	  isPrime = false;
	  break;
	}
      }

      // If candidate is still prime, add it.

      if (isPrime) {
	foundPrimes.add (candidate); // autoboxing
      }

      // Advance to the next candidate, which is the next odd number,
      // hence we add 2.

      candidate += 2;
    }
  }


  //// MAIN

  public static void main (String [] argv)
  {
    int n = 100;
    if (0 < argv.length) {
      try {
	n = Integer.parseInt (argv[0]);
      }
      catch (NumberFormatException nfx) {}
    }
    Primes pm = new Primes (n);
    pm.search ();
    pm.printPrimes ();
  }
}