/*
 *  
 * Name: prime.c
 * 
 * Purpose: find prime numbers
 *
 * Copyright: Peter Sjoberg <peters@ottawa.com>
 * 
 * Methode: quick and simple, 
 * 		check every candidate against all positive odd numbers less then sqrt(candidate)
 * 
 * Parameters: how many primes to get
 * 
 * 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>

int IsPrime (int candidate);


int IsPrime (int candidate)
{
     int i, root;
     if (candidate == 1)
         return 0;
     if (candidate == 2)
         return 0;

     if (candidate%2 == 0)
         return 1;

     root = 1+sqrt(candidate);
     for ( i=3; (i<root) && ( candidate%i !=0) ; i+=2);
     
     if (i<root)
         return 0;
     else
         return 1;
}


int main(int argc, char *argv[])
  {
     int primeCount, primeCandidate, maxNo;
     
     if ( argc > 1) 
       maxNo = atoi(argv[1]);
     else
       maxNo = 100;
     
     primeCount = 1;
     primeCandidate = 2;
     printf("Finding the first %d positive prime numbers\n", maxNo);
     printf("+-----------------------------+\n");
     printf("|      Count            Prime |\n");
     printf("+-----------------------------+\n");
//   printf("|          1                2 |\n");
//            1098765432176543210987654321
     printf("|%11d %16d |\n", primeCount, primeCandidate);
     primeCandidate++;
     while ( primeCount < maxNo )
       {
	  if ( IsPrime(primeCandidate) )
	    {
	       primeCount++;
	       printf("|%11d %16d |\n", primeCount, primeCandidate);
	    }
	  if (primeCandidate == INT_MAX) {
	     printf("We reached the limit (%d or %x) of prime candidates\n", INT_MAX, INT_MAX);
	     return 4;
	  } else {
	     primeCandidate++;
	     primeCandidate++;
	  }
       }
     printf("+-----------------------------+\n");
     return 0;
  }