/* 
   This file defines a program that finds prime numbers.  It finds
   NUMBER_TO_FIND primes and stores them in an array.  The main
   point is to find and print the NUMBER_TO_FIND-th prime.
   (NUMBER_TO_FIND is a constant that is specified at the
   beginning of the PrimeFinder class
*/


public class PrimeFinder {

   static final int NUMBER_TO_FIND = 20;  // Number of prime numbers to be found.

   static Console console = new Console();  // Console window for I/O

   static int[] primes = new int[NUMBER_TO_FIND];  // Array to hold all the primes.
   static int primeCt; // Number of primes currently found and stored in the array.


   public static void main(String[] args) {

      primeCt = 0;  // Number of primes in array starts out as zero.

      int candidate = 2;  // The number being tested to see if it is a prime

      while (primeCt < NUMBER_TO_FIND) {
         if (isPrime(candidate)) {        // If the candidate number is a prime, 
            primes[primeCt] = candidate;  //     put it in the array,
            primeCt++;                    //     and count it.
         }
         candidate++;  // Go on to the next candidate number
      }

      console.putln("The " + NUMBER_TO_FIND + "-th prime is " + primes[NUMBER_TO_FIND]);
      console.putln();
      console.putln("The first 10 primes are: ");  // (To make sure it worked.)
      for (int i = 0; i < 10; i++)
         console.putln(primes[i]);
      console.close();

   }  // end of main()


   static boolean isPrime(int N) {
         // This routine tests whether the number N is prime.  It assumes
         // that all the prime numbers between 2 and sqrt(N) have already
         // been found and placed in the array, primes.
      int S = (int)Math.sqrt(N);
      int p = 0;
      while (p < primeCt && primes[p] < S) {
          if (N % primes[p] == 0)  // If N is divisible by primes[p],
             return false;         //     then N is not prime.
         p++;
      }
      return true;  // After getting past the while loop, we know N is prime
   }


}  // end of class PrimeFinder