```/*************************************************************
/
/ 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
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);
}

```