/*************************************************************
/ trial.c 
/ 
/ A C program to calculate the first 10,000 primes 
/ 
/ 
/ Paul Soper 
/ 
/ May, 2014 
/ 
************************************************************/ 
 
/*************************************************** 
/ 
/ This program uses a standard, simple method of  
/ checking primes. 
/  
/ Make an array to hold prime numbers, and put the  
/ first prime, 2, in the first position.  Then, for  
/ each successive integer, try dividing primes in  
/ the array.  If any of them divide the candidate  
/ prime, it is not prime - move on.  If none of  
/ them divides it (up to and perhaps including  
/ the square root of the possible prime), the number  
/ is prime - add it to the array, and move on. 
/ 
/****************************************************/ 
 
#include "stdio.h" 
#include "stdlib.h"     /* because we're using exit()  
                           and malloc()*/ 
#include "math.h"       /* because we're using sqrt() */ 
 
int main() { 
  int n = 10000;     /* how many primes do we want 
			to find? */ 
 
  int* primes;       /* an array to hold the primes  
                             found, and to be the trial 
                             divisors for a new candidate */ 
 
 
  /* allocate the array */ 
  primes = (int*)malloc(sizeof(int)*10001); 
 
  /* seed the array by putting 2 in the first position */ 
  *(primes + 0) = 2; 
 
  int t = 3;         /* the first candidate prime */ 
 
  int j = 0;         /* an index counter */ 
 
 
  int is_prime = 1;  /* a flag to track whether a prime  
                        has been found */ 
 
  int found = 1;     /* the number of primes found  
                        so far  - we've already 
                        put the number 2 in the  
                        array, so set found = 1 */ 
 
  /* now start a loop, to run until we've found n  
     primes */ 
 
  while (found < n) { 
      /* start by assuming the test number is prime,  
	 then try to disprove it */ 
 
      is_prime = 1; 
 
      /* step our way through the prime array, up to  
       the square root of the candidate -  
       if we find a prime divisor for the candidate,  
       it is not a prime - unset the flag and  
       break from the loop */ 
 
      j = 0;  /* start at the beginning of the list 
		 of primes */ 
 
      while ((*(primes + j) <= (int)sqrt(t)) && (j < found)) { 
	  if ((t % *(primes + j)) == 0) { 
	      /* t is not prime because *(primes+j) divides it */ 
	      is_prime = 0; 
	      break; 
	    } 
	  ++j; 
	} 
 
      /* if we got this far without the flag being unset, 
       t is prime - add it to the array, and update the  
       found counter */ 
 
      if (is_prime == 1) { 
	  *(primes + found) = t; 
	  ++found; 
      } 
       
      ++t;  /* move to the next candidate */ 
    } 
 
  /* print the prime list */ 
 
  for (j = 0; j < n; ++j) { 
      printf("Prime %d: %d\n", j+1, *(primes + j)); 
    } 
 
  /* free the array */ 
 
  free (primes); 
 
  /* exit the program */ 
 
  return (0); 
}