/************************************************************* 
/ 
/ sieve.c 
/ 
/ A C program that calculates all the primes less than n using  
/ a Sieve of Eratosthenes 
/ 
/ Paul Soper 
/ 
/ April, 2014 
/ 
/************************************************************/ 
 
/************************************************************ 
/ 
/ This program uses a Sieve of Eratosthenes to identify prime  
/ numbers. 
/ 
/ Establish an array of numbers, 2 to n. 2 is prime, so  
/ mark all multiples of 2 as composite. Then proceed to the  
/ next unmarked number - 3 - which will be prime.  Mark as  
/ composite all multiples of 3. Proceed to the next unmarked  
/ number - 5 - which will be prime.  Mark as composite all  
/ multiples of 5.  And so on.  You can stop when you've got  
/ to sqrt(n). Then, all the unmarked numbers in the array are  
/ prime. 
/ 
/************************************************************/ 
 
#include "stdio.h" 
#include "stdlib.h" /* because we're using malloc */ 
 
int n = 250000;  /* we are going to search for primes up to n */ 
 
int main() { 
  /* we're going to use malloc to create the array of 
     integers, and primes, so that we don't have to worry  
     as much about the size */ 
 
  /* Allocate memory for an array of n integers to serve 
     as the list of all possible primes, and the list of 
     all primes. Obviously, the list of all primes will be 
     smaller, but since we're not sure as to how much 
     smaller, we're going to make them the same size */ 
 
  /* note that in this problem, we don't really need 
     to store the primes in an array of their own -  
     we can just print them - but since this algorithm 
     will be used as the basis for other problems in  
     which we do need to develop an array of primes, 
     we're going to create the array anyway */ 
 
  /* si is an array to hold the sieve */ 
  int* si = (int*)malloc(sizeof(int)*(n+2)); 
 
  /* pr is an array into which to collect the primes at 
     the end */ 
  int* pr = (int*)malloc(sizeof(int)*(n+2)); 
 
  int p = 2;  /* p will hold the primes which we are  
          using to iterate through the array,  
          striking out non-primes */ 
  int i = 0;  /* a counter */ 
  int j = 0;  /* a counter */ 
 
  /* mark all the elements in the array as candidates,  
     to start  - in this program, 1 will mean prime  
     (or not yet checked), and 0 will mean composite */ 
 
  for (i = 2; i <= n; ++i) { 
      *(si + i) = 1; 
  } 
 
  /* work our way through the primes, striking out all 
     composites*/ 
 
  for (p = 2; (p*p) < n; ++p) { 
      if (*(si + p) == 1) { 
	/* if we are here, *(si + p) is prime - use it to step  
	   through the array, striking out composites start with 
	   the first multiple, which is 2*p */ 
 
	for (j = 2*p; j <= n; j = j + p) { 
	  *(si + j) = 0; 
	} 
      } 
  } 
 
  /* now in the sieve, only primes will be marked with 1  
     - iterate through the array, copy the primes to the array 
     pr, and print them */ 
 
  j = 0; /* use the counter j to step through the 
	    primes array as we fill it */ 
 
  for (i = 2; i <= n; ++i) { 
    if (*(si + i) == 1) { 
      printf("Prime %d: %d\n", j+1, i); 
      *(pr + j) = i; 
      ++j; 
    } 
  } 
 
  /* free the allocated memory */ 
  free (si); 
  free (pr); 
  return (0); 
}