/*
 *  
 * Name: prime_array.c
 * 
 * Purpose: find prime numbers
 *
 * Copyright: Peter Sjoberg <peters@ottawa.com>
 * 
 * 
 * Methode: an array of know prime numbers is kept in memory.
 * 		any candidate is tested agains all so far known primes up to max of sqrt(candidate)
 * 
 * Parameters: how many primes to get, max is MAXPRIMES
 * 
 * Return codes:
 * 	0	: Everything is fine
 * 	1	: Max prime candidate reached, INT_MAX
 * 	2	: Max prime candidate reached, candidate^2 > max stored prime number
 * 
 * History:
 * 2001-08-13	Peter Sjoberg	Created
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or any later version.
 * 
 * This program is distributed in the hope that it will be useful
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 
 * GNU General Public License for more details.
 * http://www.gnu.org/copyleft/gpl.html
 * 
*/


#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

/* define a prime array size that can hold prime numbers up to sqrt(INT_MAX). With 32bit int 4793 is enough */
#define MAXPRIMES 4793

/* Define the format that the output should be written in, header needs a fix if changed */
#define OutputFormat "|%11d %16d |\n"

int main(int argc, char *argv[])
{
   int primeCountA, primeCount, primeLoop, primeCandidate, maxNo, root;
   int primeArray[MAXPRIMES];

   maxNo = 10000; /* default number of primes if no parameter is given */
   if ( argc > 1)
     {
	maxNo = atoi(argv[1]);
     }

   printf("Finding the first %d positive prime numbers\n", maxNo);
   printf("+-----------------------------+\n");
   printf("|      Count            Prime |\n");
   printf("+-----------------------------+\n");
   
   /* Prepare the variables */
   primeArray[0] = 2; 				/* hard to test for 2 as prime (without having to test 4,6,8...) so it's hardcode */
   printf(OutputFormat, 1, primeArray[0]);	/* print out the first prime */
   primeCountA = 1;				/* we have one prime number in the primeArray */
   primeCount = 1;				/* we have printed out one prime number */
   primeCandidate = 3;				/* Next candidate is 3 and every following odd number */
   while ( primeCount < maxNo )
     {
	root=1+sqrt(primeCandidate); /* no point in testing numbers higher then sqrt(primeCandidate) */
	if (root > primeArray[primeCountA-1]) {
	   printf("Max prime candidate is reached.\n");
	   printf("With a prime number array of %d numbers I can't test numbers higher then %d\n", MAXPRIMES, primeCandidate);
	   return 2;
	}
	
	/* test if primeCandidate is a prime by dividing with all prev known ones */
	for ( 
	     primeLoop=0 ; 
	     (primeLoop < primeCountA) && ( primeArray[primeLoop] <= root ) && (primeCandidate % primeArray[primeLoop] != 0) ;
	     primeLoop++ );

	/* Find out why it did exit, divisor found or end of loop ? */
	/* can't just test if ==0 since end of loop is outside array */
	if ( 
	    (primeArray[primeLoop] > root)  || 	    	/* End of loop, no higher no needs to be tested */
	    (primeLoop == primeCount) 			/* If end of loop, no divisor found => it's a prime */
	   )
	    {
	       if ( primeCountA < MAXPRIMES) primeArray[primeCountA++] = primeCandidate;
	       printf(OutputFormat, ++primeCount, primeCandidate);
	    }

	if (primeCandidate == INT_MAX) {
	   printf("We reached the limit (%d or %x) of prime candidates\n", INT_MAX, INT_MAX);
	   return 1;
	} else {
	   primeCandidate++;
	   primeCandidate++; /* skip a few candidates by not testing even numbers */
	}
     }
     printf("+-----------------------------+\n");
   return 0;
}